처음 보면 단순한 문자열 문제처럼 보입니다. 그런데 손으로 몇 개 적어보면, 사실은 현재 위치에서 한 자리로 볼지 두 자리로 볼지 선택이 갈리는 문제라는 걸 알 수 있습니다. 결국 핵심은 문자를 바꾸는 것이 아니라, 가능한 해석 경로를 중복 없이 세는 것입니다.
문제
숫자와 알파벳은 아래처럼 대응됩니다.
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'처럼)이라고 생각하면 이해가 쉬워집니다.
복잡도
- 시간 복잡도 — O(N)
- 공간 복잡도 — O(N)
각 위치를 한 번씩만 확인하면 되기 때문입니다.
정리
- 이 문제는 문자열 변환 문제가 아니라 경우의 수 계산 문제입니다
- 현재 위치에서 한 자리 또는 두 자리 해석이 가능합니다
- 중복 계산이 생기기 때문에 DP로 푸는 것이 적절합니다
- 핵심 예외는
'0'처리와10~26범위 확인입니다
이 글은 숫자 문자열 해석 문제를 바탕으로, 풀이 아이디어를 제 방식대로 재구성해 정리한 글입니다.