숫자 문자열 해석 경우의 수 구하기

처음 보면 단순한 문자열 문제처럼 보입니다. 그런데 손으로 몇 개 적어보면, 사실은 현재 위치에서 한 자리로 볼지 두 자리로 볼지 선택이 갈리는 문제라는 걸 알 수 있습니다. 결국 핵심은 문자를 바꾸는 것이 아니라, 가능한 해석 경로를 중복 없이 세는 것입니다.

문제

숫자와 알파벳은 아래처럼 대응됩니다.

a = 1, b = 2, ..., z = 26

숫자로 이루어진 문자열이 주어질 때, 이를 알파벳으로 해석할 수 있는 경우의 수를 구하면 됩니다.

예를 들어 "111"은 이렇게 해석할 수 있습니다.

1 1 1 → aaa
11 1 → ka
1 11 → ak

따라서 결과는 3입니다.

처음 떠오르는 생각

앞에서부터 숫자를 하나씩 읽으면 될 것처럼 보입니다. 그런데 바로 문제가 생깁니다.

"111"을 보면:

첫 글자 1만 쓸 수도 있고
앞 두 글자 11을 같이 쓸 수도 있습니다

즉, 현재 위치에서 선택지가 두 개입니다.

한 자리로 해석
두 자리로 해석

이런 분기가 계속 생기기 때문에 재귀 구조가 먼저 떠오릅니다. 그런데 같은 위치에서 시작하는 경우를 여러 번 다시 계산하게 됩니다. 그래서 이 문제는 DP(동적 계획법) 으로 푸는 것이 자연스럽습니다.

핵심 아이디어

현재 위치에서 할 수 있는 선택은 딱 두 가지입니다.

한 자리 해석

현재 문자가 '1'부터 '9'까지면 가능합니다. '0'은 혼자 해석할 수 없습니다.

두 자리 해석

현재 위치와 다음 위치를 묶어서 만든 숫자가 10에서 26 사이면 가능합니다.

'10' → j, '26' → z 는 가능합니다
'27', '01' 은 불가능합니다

매번 한 칸 갈지 두 칸 갈지 결정하는 문제로 볼 수 있습니다.

DP로 생각하기

dp[i]는 이렇게 정의할 수 있습니다.

dp[i] = i번째 문자부터 끝까지 해석하는 경우의 수

문자열 끝에 도달했다는 건 하나의 해석 경로를 완성했다는 뜻이므로 dp[n] = 1로 둡니다.

뒤에서부터 채워 가면 됩니다.

점화식

현재 문자가 '0'이면:

dp[i] = 0

현재 문자가 '1'부터 '9'까지면:

dp[i] = dp[i + 1]                     # 한 자리 해석
dp[i] += dp[i + 2]  (10에서 26 범위일 때) # 두 자리 해석

코드

아래 코드는 위 흐름을 그대로 구현한 코드입니다.

def count_decodings(message):
    n = len(message)
    dp = [0] * (n + 1)
    dp[n] = 1

    for i in range(n - 1, -1, -1):
        if message[i] == '0':
            dp[i] = 0
            continue

        dp[i] = dp[i + 1]

        if i + 1 < n and 10 <= int(message[i:i+2]) <= 26:
            dp[i] += dp[i + 2]

    return dp[0]

실행 예시

print(count_decodings("111"))   # 3
print(count_decodings("12"))    # 2  → "ab", "l"
print(count_decodings("226"))   # 3  → "bbf", "bz", "vf"
print(count_decodings("10"))    # 1  → "j"
print(count_decodings("27"))    # 1  → "bg" (27은 두 자리 해석 불가)

왜 이런 방식이 가능할까?

이 문제는 문자열을 문자로 바꾸는 문제가 아니라, 각 위치에서 앞으로 갈 수 있는 경우의 수를 누적하는 문제입니다.

계단 문제와 비슷하게 볼 수도 있습니다. 한 칸 또는 두 칸 올라갈 수 있는데, 특정 칸은 막혀 있는 상황('0'처럼)이라고 생각하면 이해가 쉬워집니다.

이 문제가 다른 DP와 다른 점

이 문제는 같은 DP라도 최대값을 구하는 유형이나 단순 이동 횟수를 세는 유형과 결이 조금 다릅니다.

핵심은 현재 위치에서 가능한 선택이 문자열 값 자체에 의해 달라진다는 점입니다.

'0'은 혼자 해석할 수 없습니다
두 자리 수는 10에서 26 범위일 때만 가능합니다
즉, 항상 한 칸/두 칸으로 갈 수 있는 문제가 아닙니다

그래서 이 문제는 단순한 “이전 두 칸의 합” 문제처럼 보이더라도, 실제로는 문자열 조건 검증이 점화식 안에 들어가는 DP라고 보는 편이 더 정확합니다.

실수하기 쉬운 부분

1. `'0'`을 독립된 문자처럼 처리하면 안 됩니다

'0'은 혼자서는 어떤 알파벳으로도 해석할 수 없습니다. 그래서 현재 문자가 '0'이면 그 위치의 경우의 수는 바로 0이 됩니다.

2. 두 자리 수 범위를 대충 보면 안 됩니다

'06', '27'처럼 길이는 두 자리여도 허용되지 않는 경우가 있습니다. 이 문제는 두 자리라는 사실보다 10에서 26 범위인지가 더 중요합니다.

3. 경우의 수 문제라는 점을 놓치기 쉽습니다

문자열을 실제로 바꿔 써 보려고 하면 흐름이 금방 복잡해집니다. 이 문제는 변환 결과를 만드는 문제가 아니라, 각 위치에서 몇 가지 방법이 가능한지 세는 문제로 보는 게 핵심입니다.

복잡도

시간 복잡도 — O(N)
공간 복잡도 — O(N)

각 위치를 한 번씩만 확인하면 되기 때문입니다.

정리

이 문제는 문자열 변환 문제가 아니라 경우의 수 계산 문제입니다
현재 위치에서 한 자리 또는 두 자리 해석이 가능합니다
중복 계산이 생기기 때문에 DP로 푸는 것이 적절합니다
핵심 예외는 '0' 처리와 10에서 26 범위 확인입니다

이 글은 숫자 문자열 해석 문제를 바탕으로, 풀이 아이디어를 제 방식대로 재구성해 정리한 글입니다.