리트코드 - Zigzag Conversion

https://leetcode.com/problems/zigzag-conversion/description/

Zigzag Conversion - LeetCode

지그재그 문자열이란 numRow가 주어졌을 때, numRow행까지 만들어진 지그재그 패턴으로 문자열을 입력받은 것을 의미한다.

지그재그 패턴으로 입력 받은 문자열 S를 line by line으로 변환하는 것이 문제에서 원하는 정답이다.

 

문제에서는 문자열을 입력해주기 때문에 이를 지그재그 패턴으로 변환할 수 있어야 하는 것이 첫 번째 단계이다.

이를 위해서 이중 리스트를 만들었다.

[
[]
[]
[]
...
]

의 형태로 이중 리스트를 생성해두고 문자열을 지그재그 패턴으로 입력받도록 하는 것이다.

지그재그 패턴으로 입력한다는 것은 지정된 행까지는 +1씩 증가한 인덱스의 리스트에 문자를 넣는 것이고 이후에는 1번째 인덱스까지 될 때 까지는 -1씩 감소한다는 것을 의미한다.

numRow == 3이라면

1 -> 2 -> 3 -> 2 -> 1 -> 2 -> 3 ... 의 순서가 될 것이다.

[
[]
[P,A,H,N]
[A,P,L,S,I,I,G]
[Y,I,R]
]

문자열 "PAYPALISHIRING"을 입력받았다고 가정할 때, 아래와 같은 형태와 동일하다.

P   A   H   N
A P L S I I G
Y   I   R

그리고 이후 해당 리스트를 line by line으로 순회해서 문자열에 추가하여 주면 된다.

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        zigzag = [[] for _ in range(numRows+1)]
        idx = 1
        change = 1
        for x in s:
            zigzag[idx].append(x)
            if idx == numRows:
                change = -1
            elif idx == 1:
                change = 1
            idx += change
        res = ""
        for i in range(1, numRows+1):
            res += "".join(zigzag[i])
        return res

이때 numRows가 1인 경우에는 지그재그가 불가능하므로, 문자열을 그대로 출력하여 주면 된다.

• 시간 복잡도: O(n)
  • for i in range(1, numRows+1) 루프는 각 행에 대해 합쳐진 문자열을 생성한다. 각 행의 길이 합은 전체 문자열 길이 n과 같으므로 시간복잡도는 O(n)이다.
• 공간 복잡도: O(n)
  • zigzag = [[] for _ in range(numRows+1)]는 각 행에 문자를 저장하므로, 전체 저장 공간은 입력 문자열의 길이 n과 동일합니다.