Leetcode Python - 6. ZigZag Conversion

Leetcode #6 - ZigZag Conversion

이번에는 특정 챕터별로 문제들을 풀어보겠습니다. string을 집중적으로 풀어보겠습니다.

리트코드의 문제 6 ‘ZigZag Conversion’을 파이썬으로 풀어 보도록 하겠습니다.

포인트는 일정 단위별로 루틴이 반복되기 때문에, 2numRows-2만큼 나누어서 라인별로 append를 하면 됩니다.

전체 코드는 아래와 같습니다.

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if not s:
            return None
        elif numRows == 1:
            return s

        divide = ['' for _ in range(numRows)]
        word = ''
        while s:
            word = s[:2*numRows-2]
            for i,w in enumerate(word):
                if i < numRows:
                    divide[i] += w
                else:
                    divide[2*numRows-i-2] += w
            s = s[2*numRows-2:]
            
        res = ''
        for d in divide:
             res += d
        return res

시간복잡도는 O(n) : 전체 길이(n)에서 2*numRows-2(상수 k)으로 나눈값만큼의 복잡도 n/k 공간복잡도는 O(n) : 전체 문자열을 divide에 입력

개선하자면 마지막 부분을 아래와 같이 바꿀 수 있습니다.

return ''.join(divide)