[코딩 테스트] 리트코드 6 - ZigZag Conversion (Medium) in Python

주어진 문자열을 numRows의 행에 따라 지그재그로 배열하여 결과문자열 리턴.

 

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

 

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

 

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3 Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4 Output: "PINALSIGYAHRPI" Explanation:

Example 3:

Input: s = "A", numRows = 1 Output: "A"

 

Constraints:

• 1 <= s.length <= 1000
• s consists of English letters (lower-case and upper-case), ',' and '.'.
• 1 <= numRows <= 1000

leetcode.com/problems/zigzag-conversion/

ZigZag Conversion - LeetCode

 

풀이

- 지그재그 배열 시 인덱스 규칙을 알아내어 풀까 했는데,

- 그 시간이나 실제로 지그재그로 배열해가며 푸는 거나 비슷할 것 같아 후자의 방법을 택했다.

 

파이썬 코드

 

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1: #예외 처리 - 한 줄이면 그대로 반환
            return s
        
        store = [[] for _ in range(numRows)] # numRows만큼 재배치할 행을 초기화
        answer = ''

        i = 0 # 문자 넣어 줄 행의 값
        toggleDown = True

        for x in s:
            store[i].append(x)
            if i == 0: # 현재 위치가 첫 번째 행이면 아래로 
                toggleDown = True
            elif i == numRows - 1: # 현재 위치가 끝 행이면 위로
                toggleDown = False
            if toggleDown:
                i += 1
            else:
                i -= 1

        for i in range(numRows):
            answer += ''.join(store[i])

        return answer

 

- 문자 하나 하나씩 살펴보므로, 시간 복잡도는 O(n)이다.

 

- 인덱스의 규칙을 찾아 푸는 것도 문자 하나 하나 살펴보는 건 똑같으므로 O(n)일 것이다.

 

- 다른 사람들의 풀이를 보니, store를 굳이 이차원 배열로 해주지 않고, 각 행을 string으로 초기화 해도 되겠다.

- 또한 행의 수가 문자열의 길이보다 크거나 같다면, 이 경우 또한 문자열 그대로 반환 가능

store = [''] * numRows #가능

if numRows == 1 or numRows >= len(s):
	return s