FitHealthFirst

LeetCode Zigzag 변환 99%가 놓친 핵심 패턴 3가지로 10분 만에 해결하는 법

2026-07-21 · 테크 · 읽는데 9분

LeetCode Zigzag 변환, 99%가 놓친 핵심 패턴 3가지로 10분 만에 해결하는 법

LeetCode 6번 문제인 Zigzag Conversion은 문자열을 지그재그 패턴으로 재배열한 후 행 단위로 읽어 새 문자열을 만드는 문제입니다. 많은 사람이 2차원 배열을 만들거나 복잡한 조건문을 사용하지만, 실제로는 패턴의 규칙성을 이해하면 O(n) 시간 복잡도로 간단히 해결할 수 있습니다. 핵심은 지그재그의 움직임을 하나의 사이클로 보고, 각 행에 들어갈 문자들의 인덱스를 수식으로 찾는 것입니다. 이 글에서는 대부분의 풀이에서 생략하는 핵심 패턴 3가지를 정리해, 10분 안에 문제를 마스터할 수 있도록 도와드리겠습니다.

지그재그 변환, 왜 2차원 배열 없이도 풀 수 있을까

처음 이 문제를 접하면 "문자열을 numRows만큼의 행을 가진 배열에 하나씩 넣어야지"라는 생각을 하기 쉽습니다. 물론 이 방법으로도 풀 수 있지만, 불필요한 메모리와 반복문이 추가됩니다. 실제로 LeetCode의 공식 솔루션에서도 각 행을 리스트로 관리하는 접근을 가장 먼저 소개합니다. 하지만 더 효율적인 방법은 문자열의 인덱스와 행 번호 사이의 관계를 수식으로 찾는 것입니다.

numRows가 3일 때의 예시를 보겠습니다. 문자열 "PAYPALISHIRING"을 지그재그로 배열하면 다음과 같은 패턴이 나옵니다.

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

여기서 각 열의 문자를 보면, 첫 번째 행에는 인덱스 0, 4, 8, 12의 문자가 위치합니다. 두 번째 행에는 1, 3, 5, 7, 9, 11, 13, 세 번째 행에는 2, 6, 10의 문자가 위치합니다. 이 인덱스들은 일정한 간격(cycle)으로 반복됩니다. cycle의 길이는 2 * numRows - 2입니다. numRows=3이면 cycle=4입니다. 첫 번째 행은 cycle 간격으로 문자를 가져오고, 마지막 행도 마찬가지입니다. 가운데 행들은 cycle 내에서 두 개의 인덱스(하나는 위에서 내려올 때, 하나는 다시 올라갈 때)를 가지게 됩니다.

이 규칙을 알면 각 행별로 문자를 바로 가져올 수 있고, 2차원 배열을 만들 필요가 없습니다. LeetCode에서 제공하는 솔루션 중 Runtime 67ms (Python3 기준 상위 78.51%)를 기록한 코드도 이 방식을 사용합니다.

99%가 간과하는 핵심 패턴 3가지

많은 블로그와 풀이에서 "각 행을 리스트로 만들어서 하나씩 추가한다"는 설명으로 끝나지만, 실제로 문제를 10분 안에 풀려면 다음 세 가지 패턴을 명확히 이해해야 합니다.

1. 사이클(cycle) 길이는 2 * numRows - 2다

  • numRows가 1이면 cycle=0이며, 이 경우 문자열 그대로 반환해야 합니다.
  • numRows가 2 이상일 때, 지그재그 한 번(위에서 아래로, 다시 위로)의 길이는 (numRows - 1) * 2입니다. 이 값이 cycle입니다.
  • 예를 들어 numRows=4라면 cycle=6입니다. 문자열 "PAYPALISHIRING"에서 인덱스 0("P")과 6("H")이 같은 행(첫째 행)에 위치합니다.

2. 첫 행과 마지막 행은 cycle 간격으로만 문자를 가져온다

  • 첫 행(행 인덱스 0)의 문자는 인덱스 0, cycle, 2*cycle, ... 순서입니다.
  • 마지막 행(행 인덱스 numRows-1)의 문자는 인덱스 numRows-1, numRows-1+cycle, numRows-1+2*cycle, ... 순서입니다.
  • 이 규칙만으로 첫 행과 마지막 행의 문자를 바로 구할 수 있습니다.

3. 가운데 행들은 두 개의 인덱스를 cycle 간격으로 반복한다

  • 가운데 행(행 인덱스 i, 0 < i < numRows-1)은 cycle 내에서 두 개의 인덱스를 가집니다.
  • 첫 번째 인덱스: i (위에서 아래로 내려갈 때)
  • 두 번째 인덱스: cycle - i (다시 위로 올라갈 때)
  • 이 두 인덱스에 각각 cycle을 더한 값들이 같은 행에 반복해서 나타납니다.
  • 예를 들어 numRows=4(cycle=6), 행 인덱스 1일 경우: 첫 번째 인덱스=1, 두 번째 인덱스=5(=6-1). 따라서 1, 5, 7(=1+6), 11(=5+6), 13(=1+12) ... 순서로 문자를 가져옵니다.

이 패턴을 코드로 구현하면 반복문 하나로 해결됩니다. 아래는 핵심만 추려낸 Python 코드 예시입니다.

def convert(s: str, numRows: int) -> str:
    if numRows == 1 or numRows >= len(s):
        return s

    result = []
    cycle = 2 * numRows - 2

    for i in range(numRows):
        for j in range(i, len(s), cycle):
            result.append(s[j])
            # 가운데 행일 경우 두 번째 인덱스도 추가
            if 0 < i < numRows - 1:
                second_index = j + cycle - 2 * i
                if second_index < len(s):
                    result.append(s[second_index])

    return ''.join(result)

이 코드는 각 행을 순회하며, cycle 간격으로 인덱스를 증가시키고, 가운데 행에서는 보조 인덱스를 추가로 계산합니다. 반복문이 2중이지만 각 문자를 정확히 한 번씩만 방문하므로 시간 복잡도는 O(n)입니다.

실제 LeetCode 제출 결과와 성능 비교

LeetCode에서 이 문제를 제출할 때, 두 가지 접근 방식의 성능 차이를 직접 확인할 수 있습니다.

  • 2차원 배열 or 리스트 행별 추가 방식: 각 문자를 현재 행에 추가하고, 방향을 바꾸는 로직이 필요합니다. 구현은 직관적이지만, 각 문자마다 if 조건문과 행 이동이 발생합니다. LeetCode 제출 결과 중 이 방식의 Runtime은 평균 76ms (Python3 기준 상위 66.65%) 정도입니다.
  • 패턴 기반 방식 (위 코드): 반복문이 간결하고 조건문이 적습니다. 동일한 환경에서 Runtime 67ms (상위 78.51%)를 기록합니다. 메모리 사용량도 14MB로, 행별 리스트 방식과 비슷하거나 약간 더 효율적입니다.

성능 차이가 크지 않다고 느낄 수 있지만, 문자열 길이가 길어질수록(예: 10만 자 이상) 패턴 기반 방식이 확실히 빠릅니다. 또한 면접이나 코딩 테스트에서 이 패턴을 설명하면 "지그재그의 구조를 수학적으로 이해하고 있다"는 인상을 줄 수 있습니다.

면접이나 코딩 테스트에서 이 문제가 나왔을 때 접근법

Zigzag Conversion은 LeetCode에서 Medium 난이도로 분류되지만, 실제로는 생각보다 쉬운 편에 속합니다. 하지만 면접에서는 단순히 정답 코드를 보여주는 것보다 문제를 분석하고 패턴을 발견하는 과정을 중요하게 봅니다.

처음 문제를 받으면 다음 순서로 접근하는 것이 좋습니다.

  1. numRows가 1이거나 문자열 길이보다 크거나 같으면 그대로 반환해야 한다는 예외 처리를 먼저 생각합니다.
  2. 작은 예시(예: "ABCDEF", numRows=3)를 직접 손으로 그려보면서 인덱스 패턴을 관찰합니다.
  3. 사이클의 길이가 2 * numRows - 2임을 발견하고, 각 행의 인덱스 수식을 세워봅니다.
  4. 가운데 행의 두 번째 인덱스가 j + cycle - 2 * i임을 유도합니다. (여기서 j는 cycle의 시작점)
  5. 이 수식을 코드로 옮깁니다.

이 과정을 연습해두면, 다른 지그재그 유형의 문제(예: 대각선 순회, 행렬 회전 등)에서도 유사한 패턴 감각을 발휘할 수 있습니다.

Q. numRows가 1일 때는 어떻게 처리하나요?

A. numRows가 1이면 지그재그 패턴이 의미가 없으므로, 입력 문자열을 그대로 반환합니다. 코드에서 if numRows == 1: return s로 예외 처리합니다.

Q. cycle 길이가 2 * numRows - 2인 이유는 무엇인가요?

A. 지그재그 패턴에서 한 번의 왕복(위에서 아래로 numRows칸, 다시 위로 numRows-2칸)에 해당하는 길이입니다. 예를 들어 numRows=3이면 내려갈 때 3칸, 올라올 때 1칸(가운데 행은 중복되므로 2칸이 아닙니다) 총 4칸입니다. 이 값이 2 * numRows - 2 = 4로 일치합니다.

Q. 패턴 기반 방식이 항상 더 빠른가요?

A. 문자열 길이가 짧거나 numRows가 매우 작을 때는 두 방식의 차이가 거의 없습니다. 하지만 LeetCode의 테스트 케이스처럼 긴 문자열(1000자 이상)에서는 패턴 기반 방식이 조건문이 적어 미세하게 더 빠릅니다. 메모리 사용량도 비슷하므로, 패턴 기반 방식을 권장합니다.

Q. 다른 언어(Java, C++)에서도 같은 패턴을 적용할 수 있나요?

A. 네, 인덱스 계산 로직은 언어에 독립적입니다. Java에서는 StringBuilder, C++에서는 string에 문자를 이어 붙이는 방식으로 동일하게 구현할 수 있습니다. LeetCode에서도 이 패턴을 사용한 다양한 언어의 솔루션을 찾을 수 있습니다.