[LeetCode] Zigzag Conversion 풀이 및 후기

개요

LeetCode
문제 명	Zigzag Conversion
난이도	Medium
체감 난이도	Medium
풀이 시간	1시간 정도

 

문제 설명

문자열 "PAYPALISHIRING"은 다음과 같이 주어진 수의 행에 지그재그 패턴으로 작성됩니다.

주어진 행의 수가 3이라면 다음과 같은 지그재그 패턴이 나옵니다.

지그재그 패턴

주어진 문자열을 다음과 같은 지그재그 패턴으로 바꿨다면, 행을 단위로 문자를 읽어 출력하면 됩니다.

출력 값은 PAHNAPLSIIGYIR이 됩니다.

입출력 예시

입출력 예시 1
입력 값	s = "PAYPALISHIRING" numRows = 3
기대 값	PAHNAPLSIIGYIR
설명	위에서 설명함

 

제약 조건

• 1 <= s.length <= 1000
• s는 영문자(소문자, 대문자)로 구성됩니다.
• 1 <= numRows <= 1000

 

풀이

이 문제를 보고 주어진 문자열을 지그재그 패턴으로 정렬하고 위에서부터 한 행씩 읽어내려오면 되는 간단한 문제라고 생각했다.

지그재그 패턴을 만드는데 시간이 꽤 걸렸던 거 같다.

 

내가 생각한 알고리즘은 numRows를 활용하여 문자열 슬라이스를 하여 해결하는 것이었다.

 

최종 제출코드

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        result = ""
        idx = 0
        arr = []
        while idx < len(s):
            end = idx + numRows
            arr.append(s[idx:end])
            if numRows > 2:
                for _ in range(numRows - 2):
                    if end + _ >= len(s): break # 문자열 초과 참조 에러 방지
                    newArr = ["?" for _ in range(numRows)]
                    newArr[numRows - 2 - _] = s[end + _]
                    arr.append("".join(newArr))
                idx += numRows + (numRows - 2)
            else:
                idx += numRows
        
        for i in range(numRows):
            for item in arr:
                if i >= len(item): break
                if item[i] != "?": result += item[i] 
        
        return result
        
s = Solution()
s.convert("PAYPALISHIRING", 3)

 

1. 주어진 문자열을 처음부터 끝까지 순회하고 분기점을 만들기 위해 idx 변수를 활용한다.
2. idx는 0부터 시작하고, end는 idx + numRows로 설정하여 지그재그 패턴에 필요한 구조를 만든다.
   1. end를 idx + numRows로 하게 된 이유는 PAY, P, ALI, S... 형태로 글자를 numRows단위로 슬라이싱하고 지그재그에 쓰이는 글자는 따로 관리하기 위함이다.
3. s[idx:end]를 활용하여 원하는 만큼 문자열을 슬라이싱 하고, arr 배열에 추가한다.
4. numRows가 2면 지그재그 패턴에 남는 공간이 없기 때문에, 알고리즘을 적용하지 않는다.
5. numRows가 3 이상이면,
   1. numRows 개수 만큼의 "?"로 이루어진 배열을 만든다.
   2. 지그재그 패턴에 들어갈 문자열을 삽입한다.
6. 이 과정을 모두 거치면 결과는 다음과 같다.

numRows가 3일 때

numRows가 4일 때

여기까지 만들었다면 이제 한 행씩 출력만 해주면 문제의 답이 출력된다.

 

결과 화면

음,,, 아무래도 반복문이 많다보니 효율성이 떨어진다.

 

 

회고

문제를 푸는 것에 있어서 큰 어려움은 없었지만, 효율성이 생각보다 좋지 못해서 아쉬웠다.

다음 번에는 반복문을 최소화하고, 시간 복잡도가 낮은 자료구조 알고리즘에 대해 더 생각해봐야겠다.