6. Zigzag Conversion

1. Description

• The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

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

• And then read line by line: "PAHNAPLSIIGYIR"
• Write the code that will take a string and make this conversion given a number of rows:

2. Example

Example 1

Input: s = “PAYPALISHIRING”, numRows = 3 Output: “PAHNAPLSIIGYIR”

Example 2

Input: s = “PAYPALISHIRING”, numRows = 4 Output: “PINALSIGYAHRPI” Explanation:

Note

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

Example 3

Input: s = “A”, numRows = 1 Output: “A”

3. Solution

1. 첫번째 풀이
   • Runtime: 9ms
   • 설명
     • 지그재그로 문자를 넣기 위해 2차원 배열을 사용한다.
     • idx = 0는 [0,0]부터 시작하므로 index를 지정한다.
       • 여기서 index는 2차원 배열안의 배열의 위치를 나타내준다.
     • d = 1 d는 Direction이다.
       • 배열이 0부터 시작하므로 내려가야하므로 d=1로 지정한다.
     • numRows열이 1일 경우, 첫번째 줄만 사용되니 s에 있는 문자열이 그대로 나타난다.
     • s의 길이가 numRows보다 작거나 같으면 문자열로 한 줄로 나타낼 경우 s문자열과 같게 나타난다.
     • for문
       • 처음에는 무조건 [0,0]에서 시작하므로 for문 맨위에 써둔다.
       • idx가 마지막 행일 경우 다시 올라와야 하므로
         • if idx == numRows - 1는 0부터 시작하여 numRows - 1까지 나타난다.
         • 이 경우 맨 아래에 있으므로 다시 올라가야한다.
         • 이 시점 idx는 numRows - 1와 같으므로 올라가기 위해서는 -1로 정해줘야한다.
       • idx가 첫번째 행일 경우 내려가야 하므로
         • if idx == 0는 0번째 행이 결국에 첫번째 행이르모 이 위에 다른 행은 없다.
       • idx += d를 통해 d = 1이거나 d = -1일 경우 더하면서 idx값이 바뀐다.
     • 처음 for문을 나오게 되면 2차원 배열로 되어 있을것이다.
     • 2차원 배열을 문자열로 바꿔주기 위해서는 ''.join()을 두 번 써주면 된다.
       • 처음 쓸 때는 리스트안의 리스트를 하나의 리스트로 만들어주기 위함이다.
       • 두번째는 리스트를 문자열로 바꿔주는 것이다.

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        ans_list = [[] for _ in range(numRows)]
 
        idx = 0 # Index
        d = 1 # Direction
 
        if numRows == 1 or len(s) <= numRows:
            return s
 
        for char in s:
            ans_list[idx].append(char)
            if idx == numRows - 1:
                d = -1
            elif idx == 0:
                d = 1
            idx += d
 
        for i in range(numRows):
            ans_list[i] = ''.join(ans_list[i])
 
        return ''.join(ans_list)

• 📌이 문제는 idx와 d를 설정하는게 처음 접근할 때 해야 하는 거 같다.
  • idx를 통해 현재 위치를 나타내고, d를 통해 방향을 정하며 이를 통해 for문을 한 번 돌리지만 두 번 돌리는거와 같은 기능을 가지게 된다.
• 최적화된 코드

# from collections import defaultdict
 
class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1 or len(s) <= numRows:
            return s
 
        ans_list = [""] * numRows
 
        idx = 0
        d = 1
 
        for char in s:
            ans_list[idx] += char
            if idx == 0:
                d = 1
            elif idx == numRows - 1:
                d = -1
            idx += d
        
        return ''.join(ans_list)

• 2차원 배열로 굳이 안만들고 1차원 배열로 한 줄로 만들었다.
• 친구(광성)이가 말해줬던 컴퓨터가 데이터를 읽을 때 하나씩 보니 굳이 2차원 배열로 시각적으로 나타낼 필요는 없다.
• 하지만 우리의 이해를 돕는데 도움이 되기 때문에 2차원 배열을 쓴다.

4. What I Learned

References

• Chat GPT
• Youtube - 답지