LeetCode의 Zigzag Conversion 문제는 문자열을 지그재그 패턴으로 재배치한 뒤, 행 단위로 읽어 새로운 문자열을 만드는 문제입니다. 이 글에서는 실제로 많이 사용되는 세 가지 풀이 방식을 비교하며, 각각의 장단점을 코드와 함께 정리해 보았습니다. 결론부터 말하면, 2차원 배열을 만들 필요 없이 행 인덱스의 방향 전환만 제어하는 방식이 가장 간단하고 빠릅니다.
이 문제를 어렵게 만드는 핵심, 행 인덱스 방향 전환
지그재그 변환에서 가장 중요한 부분은 문자가 어느 행에 들어가는지를 추적하는 일입니다. 문자열 PAYPALISHIRING을 numRows = 3으로 변환할 때, 문자가 배치되는 행의 순서는 0 → 1 → 2 → 1 → 0 → 1 → 2 … 로 움직입니다. 즉, 위에서 아래로 내려갔다가 바닥에 닿으면 다시 위로 올라가는 패턴이 반복됩니다.
이 흐름을 코드로 옮기려면 현재 행 인덱스와 방향을 나타내는 변수가 필요합니다. 행 인덱스가 0이나 numRows - 1에 도달할 때마다 방향을 반전시키면 되는데, 이 방향 전환을 놓치면 결과가 완전히 틀어집니다. 특히 numRows = 2일 때는 행 순서가 0 → 1 → 0 → 1로 단순하지만, 방향 전환 로직이 제대로 동작하는지 확인하기 좋은 테스트 케이스입니다.
풀이 1 각 행을 리스트로 두고 순서대로 채우기
가장 직관적인 방법은 numRows 개수만큼 리스트를 만들고, 문자열을 순회하면서 현재 행에 문자를 하나씩 추가하는 것입니다. 행 인덱스는 방향 변수를 통해 증가하거나 감소하며, 끝에 도달하면 방향을 바꿉니다.
def convert(s: str, numRows: int) -> str:
if numRows == 1 or numRows >= len(s):
return s
rows = [''] * numRows
current_row = 0
going_down = False
for char in s:
rows[current_row] += char
if current_row == 0 or current_row == numRows - 1:
going_down = not going_down
current_row += 1 if going_down else -1
return ''.join(rows)
이 방식은 2차원 배열의 크기를 계산할 필요가 없고, 빈 공간을 건너뛰는 로직도 필요 없습니다. 각 행에 실제로 문자가 들어간 위치만 존재하므로, 마지막에 리스트를 순서대로 합치기만 하면 됩니다. 시간 복잡도는 O(n)으로 문자열의 길이에 비례하며, 코드도 짧아서 실수가 적습니다.
풀이 2 2차원 배열을 만들고 규칙으로 인덱스 계산하기
일부 풀이에서는 2차원 배열을 만든 뒤, 지그재그 패턴의 규칙을 수식으로 도출해 문자를 배치합니다. 예를 들어 numRows = 5일 때 0번째 행에는 인덱스 0, 8, 16번째 문자가 들어가고, 1번째 행에는 1, 7, 9, 15번째 문자가 들어가는 식입니다.
def convert(s: str, numRows: int) -> str:
if numRows == 1 or numRows >= len(s):
return s
result = []
cycle_len = 2 * numRows - 2
for row in range(numRows):
for i in range(row, len(s), cycle_len):
result.append(s[i])
if row != 0 and row != numRows - 1:
next_idx = i + cycle_len - 2 * row
if next_idx < len(s):
result.append(s[next_idx])
return ''.join(result)
이 방식은 한 번의 순회로 결과를 만들 수 있다는 장점이 있지만, 행마다 건너뛰는 인덱스 규칙을 이해해야 합니다. 초보자 입장에서는 cycle_len과 next_idx 계산이 헷갈릴 수 있고, numRows가 1이거나 문자열 길이가 짧은 경우를 처리하는 조건을 빼먹으면 오류가 발생합니다. 시간 복잡도는 O(n)이지만, 규칙을 잘못 적용하면 히든 테스트 케이스에서 걸리기 쉽습니다.
풀이 3 행 길이를 하드코딩하거나 불필요한 연산을 줄이는 방법
검색해 보면 행 길이를 수식으로 계산하려다가 실패한 사례가 꽤 많습니다. 실제로 s.length가 최대 1000이므로 행 길이를 1001로 하드코딩하는 것도 가능하지만, 이렇게 하면 코드가 복잡해지고 메모리도 낭비됩니다. 더 깔끔한 대안은 List<Character>[] 같은 동적 구조를 활용하는 것입니다.
def convert(s: str, numRows: int) -> str:
if numRows == 1 or numRows >= len(s):
return s
rows = [[] for _ in range(numRows)]
current_row = 0
step = 1
for char in s:
rows[current_row].append(char)
if current_row == 0:
step = 1
elif current_row == numRows - 1:
step = -1
current_row += step
return ''.join(''.join(row) for row in rows)
이 방식은 리스트를 사용해 문자를 추가하는 면에서 풀이 1과 유사하지만, 방향 전환을 step 변수 하나로 처리합니다. current_row가 0이면 step을 양수로, numRows - 1이면 음수로 바꾸는 방식입니다. 코드가 단순해지고 실행 시간도 3ms 수준으로 줄어드는 것을 확인할 수 있습니다.
초반에 걸러야 하는 조건, 왜 중요할까
세 가지 풀이 모두 공통적으로 numRows == 1이거나 numRows >= len(s)인 경우를 먼저 처리합니다. 이 조건을 빼먹으면 ArrayIndexOutOfBounds 예외가 발생하거나, 불필요한 연산이 들어가게 됩니다.
numRows == 1: 지그재그로 변환해도 결과가 원본 문자열과 동일합니다.numRows >= len(s): 문자열의 길이보다 행 수가 많으면, 각 문자가 서로 다른 행에 하나씩만 배치되어 결과가 원본과 같아집니다.
이 조건을 초반에 걸러 주면 이후 로직이 훨씬 안전해지고, 테스트 케이스에서 불필요한 실패를 방지할 수 있습니다.
어떤 풀이를 선택하는 것이 좋을까
문제를 처음 접할 때는 눈에 보이는 패턴부터 따라가는 것이 오히려 빠릅니다. 행 인덱스를 하나씩 이동하면서 방향만 바꿔주는 방식이 가장 직관적이고 실수도 적습니다. 2차원 배열이나 인덱스 규칙을 수식으로 풀려다가 시간을 낭비하는 경우가 많은데, 리스트를 활용하면 문자를 넣을 위치를 계산하지 않아도 됩니다.
시간 복잡도는 세 가지 모두 O(n)으로 동일하지만, 코드의 단순함과 가독성에서 차이가 큽니다. 실제로 LeetCode 토론 게시판에서도 3ms로 통과한 풀이들은 대부분 행 인덱스 방향 전환 방식입니다. 문제를 풀 때는 단순히 해결하는 것에서 나아가, 그 해결책이 얼마나 효율적인지를 고려하는 습관이 중요합니다. 반복문을 최소화하고 시간 복잡도가 낮은 자료구조를 선택하는 것이 다음 단계로 가는 길입니다.
Q. numRows = 1일 때 왜 바로 s를 반환하나요?
지그재그로 변환할 행이 하나뿐이므로, 문자가 모두 같은 행에 배치됩니다. 결과적으로 원본 문자열 그대로가 출력되기 때문에 예외 처리가 필요합니다.
Q. 문자열 길이가 numRows보다 짧은 경우는 어떻게 되나요?
이 경우 각 문자가 서로 다른 행에 하나씩만 배치됩니다. 변환해도 결과가 원본과 동일하므로, 바로 s를 반환하는 것이 안전합니다.
Q. 입력 s의 길이가 1000을 넘을 수 있나요?
문제 제약 조건에 따르면 s.length는 최대 1000입니다. 따라서 행 길이를 하드코딩하는 방법도 가능하지만, 리스트를 쓰는 편이 더 깔끔합니다.
Q. 이 문제에서 가장 흔한 실수는 무엇인가요?
행 인덱스가 0과 numRows - 1을 오갈 때 방향 전환을 놓치는 경우가 많습니다. 특히 마지막 행에 도달했다고 바로 방향을 반전시키지 않고, 다음 문자에서 반전시키면 결과가 틀어집니다.