Note
문자열을 numRows개의 행에 지그재그로 쓴 뒤, 행 순서대로 이어 붙이는 변환의 원리입니다. 행 인덱스를 위→아래→위로 바꿔 가며 문자를 배치하면 됩니다.
문제 상황
문자열 s를 지그재그로 씁니다.
- numRows개의 행이 있음 (0번 ~ numRows-1번)
- 문자는 0행 → 1행 → … → (numRows-1)행으로 내려갔다가, 그다음 (numRows-2)행 → … → 0행으로 올라갔다가, 다시 내려가는 식으로 반복
- 맨 위·맨 아래에서 방향이 바뀜
그 후 0행, 1행, …, (numRows-1)행 순서로 각 행의 문자를 이어 붙인 문자열이 정답입니다.
지그재그가 의미하는 것
- 아래로: 행 인덱스가 +1 (0 → 1 → … → numRows-1)
- 위로: 행 인덱스가 -1 (numRows-1 → … → 0)
- 맨 위(0) 또는 맨 아래(numRows-1) 에 도달하면 방향 전환
즉, 현재 행 인덱스와 방향(offset: +1 또는 -1) 만 관리하면 됩니다.
시뮬레이션 방식
- 행별로 문자를 모을 공간 준비 —
arr[row]= 그 행에 들어갈 문자들의 리스트 - idx = 0, offset = +1 로 시작
- s의 각 문자에 대해:
arr[idx]에 문자 추가- idx가 numRows-1이면 방향을 위로 → offset = -1
- idx가 0이면 방향을 아래로 → offset = +1
- idx += offset
- idx가 numRows가 되면 1 줄이고, -1이 되면 0으로 보정 (경계 처리)
- 모든 행의 문자를 순서대로 이어 붙여 반환
예시: s = “PAYPALISHIRING”, numRows = 3
| 행 0 | 행 1 | 행 2 |
|---|---|---|
| P | A | Y |
| P | ||
| A | L | I |
| S | ||
| H | I | R |
| I | ||
| N | G |
행 순서로 읽으면: “PAHNAPLSIIGYIR”
요약
| 항목 | 내용 |
|---|---|
| 지그재그 | 0행 → … → (numRows-1)행 → … → 0행 반복 |
| 방향 전환 | idx가 0이면 +1, numRows-1이면 -1 |
| 행별 저장 | 리스트의 리스트(행별 문자 리스트) |
| 출력 | 0행 + 1행 + … + (numRows-1)행 |
관련 문제
- LeetCode 6: Zigzag Conversion - 코드 구조