[LeetCode] 6 | Zigzag Conversion

6 | Zigzag Conversion
https://leetcode.com/problems/zigzag-conversion/

 

 

 

 

 

작성 코드

 

접근 방법

 

1. 각 행에 반복되는 규칙을 찾아 인덱스로 저장하자

 

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        elif numRows == 2:
            indexes = []
            indexes += [s[index] for index in range(0, len(s), 2)]
            indexes += [s[index] for index in range(1, len(s), 2)]
            return ''.join(indexes)
            
        indexes = []
        
        repeat = numRows + (numRows - 2)
        indexes_first = [index for index in range(0, len(s), repeat)]
        indexes_last = [index for index in range(numRows - 1, len(s), repeat)]
        
        indexes_middle = []
        for start_index in range(1, numRows - 1):
            for index in range(start_index, len(s), repeat):
                indexes_middle += [index]
                if index + (repeat - (2 * start_index)) < len(s):
                    indexes_middle += [index + (repeat - (2 * start_index))]
                    
        return (''.join([s[index] for index in indexes_first] + [s[index] for index in indexes_middle] + [s[index] for index in indexes_last]))

 

• 반복되는 부분(repeat) = 첫 인덱스 ~ 첫째행으로 오기 바로 직전의 인덱스 = numRows + (numRows - 2)
• 첫째행은 시작 값이 0, repeat 만큼 반복
• 마지막행은 시작 값이 numRows, repeat 만큼 반복
• 가운데행은 1~(numRows-1) 까지 시작 인덱스로 for 문을 돌 때 / [시작 인덱스, 시작인덱스 + (repeat - (2 * start_index))] 를 repeat 만큼 반복
• 단, '시작인덱스 + (repeat - (2 * start_index)' 값이 문자열의 길이를 초과할 수 있기 때문에 확인해주는 작업 필요
• numRows가 1, 2인 경우는 위의 규칙이 적용되지 않아 예외처리 필요

• 모든 테스트 케이스를 통과하긴 했지만, numRows의 길이에 대한 예외처리를 해줘야하고 코드가 난잡해 좋은 코드는 아니라는 생각이 듦

 

 

이상 코드

 

class Solution(object):
    def convert(self, s, numRows):
        step = (numRows == 1) - 1  # 0 or -1  
        rows, idx = [''] * numRows, 0
        for c in s:
            rows[idx] += c
            if idx == 0 or idx == numRows-1: 
                step = -step  #change direction  
            idx += step
        return ''.join(rows)
        
# [출처] https://leetcode.com/problems/zigzag-conversion/discuss/3404/Python-O(n)-Solution-in-96ms-(99.43)

 

• numRows 크기의 rows 배열 생성
• 문자열 s를 for문으로 돌면서 rows[idx]에 더해줌
• idx 값이 0 이거나, (numRows - 1) 이면, 즉 끝 값이면, step의 부호를 바꾸어 방향을 바꿔줌 / step의 값은 0, -1, 1 중 하나
• idx에 step 을 더해주며 값 갱신
• ex) numRows 가 3이라면 idx 값은 0, 1, 2, 1, 0 , 1, 2 ... 반복
• numRows가 1이라면, step 은 0이 되어 idx 값은 계속 0이 됨