[LeetCode] 6. Zigzag Conversion

6. Zigzag Conversion

Medium

 

 

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:

string convert(string s, int numRows);

 

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I

Example 3:

Input: s = "A", numRows = 1
Output: "A"

 

Constraints:

• 1 <= s.length <= 1000
• s consists of English letters (lower-case and upper-case), ',' and '.'.
• 1 <= numRows <= 1000

 

---

문제 풀이

• 문장 한개와 행의 갯수가 주어진다. 
• 문장에서 순서대로 row갯수에 맞에 글자가 저장된다.

 

• 그리고 다음 행의 숫자로 넘어갈 때는 거꾸로 저장이된다. 
• 예를 들어 PAYPALISHIRING, numRows가 3이면,
  • 0: P
    1: A
    2: Y
• 위와 같이 한 행씩 문자가 들어간다.
• 그리고 행의 갯수만큼 글자를 배정하면 행의 숫자를 거꾸로 돌아가면서 문자를 행에 넣는다.
• 첫번째 행과 마지막 행은 배제해야한다. 

 

• 예를 들면
  • 0: P
    1: A
    2: Y
• PAY 다음에는 P를 넣어야하는데 이미 2까지 문자를 배정했으니, 거꾸로 1에 저장해야한다. 
  • 0: P
    1: A P
    2: Y
• 위의 과정 다음에는 행의 번호가 시작점으로 간다. 
  • 0: P    A
    1: A P
    2: Y
• A가 첫번째 행에 저장되고 나머지 과정은 위에서 예를 든 설명과 같이 반복된다. 

 

• 문제 제한을 살펴보면, 문장의 최대길이가 1000이기 때문에 브루트 포스로 문제를 풀어도 된다.
• 투포인터 식으로 문제를 푼다면, 기존의 인덱스 idx와 행의 번호를 조작할때 사용할 d를 선언한다.
• 인덱스를 늘리거나 줄이면서 해당 리스트에 문자를 넣자.
• 행의 번호를 조작할때 1을 더하거나 1을 빼어 행의 번호를 바꿔야한다.
• 맨마지막 행번호에 다다랐을때는 d를 -1로 바꿔주고 맨처음 인덱스에 다다랐을때는 1로 바꿔준다.
• d 값을 계속해서 idx값에 더해주는 식으로 문제를 푼다.
• if 문에서 첫번째 행의 번호와 마지막 행의 번호가 먼저 처리되고 문자를 답 리스트 문자열에 넣기 때문에 문제 없이 진행된다.

소스 코드

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        ans = ['' for _ in range(numRows)]
        idx, d = 0, 1
        for i in range(len(s)):
            ans[idx] += s[i]
            if idx == numRows - 1:
                d = -1
            elif idx == 0:
                d = 1
            idx += d
        return ''.join(ans)