LeetCode 6(Zigzag Conversio, Python)

1. 문제 링크

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

2. 문제 설명

• 문자열과 줄 개수가 주어졌을 때, 이를 ↓↗↓↗ 로 반복 배열 한 후, 위에서 아래로 이어붙여서 반환
  
  • 예시) str= "PAYPALISHIRING", numRows = 3이 주어지면 
    • P      A      H     N
    • A  P  L  S   I  I   G
    • Y       I       R
    • 로 배열한 후, 위에서 아래로 이어붙여서 "PAHNAPLSIIGYIR"를 반환

3. 처음 풀이

• 46ms(97.08%), 16.48mb(36.12%)
• 문제 이름대로 지그재그 움직이는 아이디어
• 현재 가로 줄이 몇 번째인지 나타내는 변수 position과 위로 갈지 아래로 갈지 방향을 나타내는 변수 direction에 0, 1을 초기 할당함
• 현재 위치한 가로 줄에 문자를 입력, 이후 direction 방향으로 이동, 마지막 줄에 도착하면 direction 을 -1로 바꾸어주고 첫 줄에 도착하면 direction을 1로 바꾸어주어 지그재그를 구현.
• 예외 케이스로 numRows 가 1인 경우에는 direction을 0으로 변경
• 문자를 하나 꺼낼 때 list의 마지막 원소를 꺼내는 .pop()을 사용하고 싶어서 주어진 문자열을 역순으로 뒤집은 후 리스트로 저장

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        s = list(s[::-1]) #문자열을 [::-1]로 역순, list로 저장
        result = ['' for x in range(numRows)] #각각이 가로줄 하나를 나타내는 빈 문자열을 numRows 개수 만큼 result 리스트에 저장
        
        position, direction = 0, 1 #현재 가로줄 index를 나타내는 position, 이동 방향 나타내는 direction
        while s: #리스트에 원소가 남아 있는 동안 반복 즉, 주어진 문자열을 모두 쓸 동안 반복
            result[position] += s.pop() #현재 가로줄에 한 글자 저장
            if numRows == 1: #1줄이면 지그재그 이동 필요 없으므로 이동 =0
                direction = 0
            elif position == 0: #시작 줄에 도착했다면 아래로 이동해야하므로 이동 =1
                direction = 1
            elif position == numRows-1: #마지막 줄 도착했다면 위로 이동해야하므로 이동 =-1
                direction = -1
            position += direction #정해진 방향으로 이동
        
        return ''.join(result) #리스트에 저장된 각각의 가로줄 문자열을 한 문자열로 합치기

 

4. 다른 풀이

• 일단 기존 풀이와 시간 복잡도, 공간 복잡도는 같다. 기존 풀이가 코드 가독성이 더 좋음
• n개의 줄로 만들 때 처음과 마지막 줄에 들어가는 문자의 인덱스는 2(n-1)씩 커지는 것을 알 수 있고
• 나머지 가로 줄은 홀수 번째와 짝수 번째끼리 따로 보면 마찬가지로 2(n-1)씩 커짐을 알 수 있음
• 이때 가로 줄의 1번째 2번째 문자열의 인덱스를 더하면 2(n-1)임을 이용하면 각 가로 줄에 와야하는 문자열의 index를 모두 파악할 수 있음.
• 수학에서 두 등차수열을 번갈아 나열했을 때 일반항을 찾는 상황
• 작동 방식은 직관적이나 코드 가독성은 떨어진다.

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        ans=""
        increment = 2*(numRows-1)
        for i in range(0,numRows):
            for j in range(i,len(s),increment):
                 ans+=s[j]
                 if (i > 0 and i < numRows-1 and j+increment-2*i < len(s)):
                     ans+=s[j+increment-2*i]
        return ans

 

4. 다른 풀이2

• numRow가 3이면 1,2,3,2가 반복이 되고, numRow가 4이면 1,2,3,4,3,2 가 반복이 되므로
• 이를 turnlist라는 list에 넣은 뒤, turnlist의 element를 key로 하고 이에 대응되는 문자열을 value로 하는 
• history_dict을 생성 후, history_dict의 values를 ''.join하여 반환

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        history_dict = {}
        turnlist = []
        for i in range(numRows):
            turnlist.append(str(i))

        turnlist = turnlist + turnlist[::-1][1:len(turnlist)-1]

        for index,i in enumerate(s):
            key = index % len(turnlist)
            if turnlist[key] not in history_dict:
                history_dict[turnlist[key]] = i 
            else:
                history_dict[turnlist[key]] += i 

        return ''.join(history_dict.values())

 

5. 배운점

• pointer의 위치와 방향을 분리해서 생각하면 편할 때가 있음.