A부터 Z까지의 알파벳으로 이루어진 메시지가 다음과 같은 매핑 규칙을 사용해 숫자로 인코딩되어 있다고 가정해 보겠습니다 — 'A' → 1, 'B' → 2 ... 'Z' → 26. 이때 숫자로만 구성된 비어 있지 않은 문자열이 하나 주어지면, 해당 문자열을 디코딩할 수 있는 총 경우의 수를 구해야 합니다.
예를 들어 문자열이 "12"라면, 이는 "AB"(1, 2) 또는 "L"(12)로 해석될 수 있으므로 가능한 디코딩 방법은 두 가지입니다. 따라서 정답은 2가 됩니다.
문제 해결 접근 방식
이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 위치에서 한 자리 숫자 또는 두 자리 숫자로 디코딩할 수 있는지를 확인하고, 그 경우의 수를 누적하는 것입니다. 알고리즘의 단계는 다음과 같습니다.
- 동적 계획법을 사용하여 문제를 해결합니다.
- n := 문자열 s의 길이
- dp := 길이가 n이고 모든 요소가 0으로 초기화된 배열
- s[0]이 '0'이 아니라면 dp[0] := 1로 설정합니다.
- i를 1부터 n-1까지 반복합니다.
- x := s[i]를 정수로 변환한 값, y := s의 인덱스 i-1부터 i+1까지 부분 문자열을 정수로 변환한 값
- x가 1 이상 9 이하이면 dp[i] := dp[i] + dp[i-1]
- y가 10 이상 26 이하이면:
- i-2가 0 이상이면 dp[i] := dp[i] + dp[i-2], 그렇지 않으면 dp[i]에 1을 더합니다.
- dp 배열의 마지막 요소를 반환합니다.
Python 예제 코드
다음 구현을 통해 더 자세히 이해해 보겠습니다.
class Solution(object):
def numDecodings(self, s):
n = len(s)
dp = [0 for i in range(n)]
if s[0]!='0':
dp[0]=1
for i in range(1,n):
x = int(s[i])
y = int(s[i-1:i+1])
if x>=1 and x<=9:
dp[i]+=dp[i-1]
if y>=10 and y<=26:
if i-2>=0:
dp[i]+=dp[i-2]
else:
dp[i]+=1
return dp[-1]
ob1 = Solution()
print(ob1.numDecodings("226"))
입력
"226"
출력
3
결과 분석
입력값 "226"은 다음 세 가지 방법으로 디코딩할 수 있습니다.
- "BBF" → (2, 2, 6)
- "BZ" → (2, 26)
- "VF" → (22, 6)
따라서 출력 결과는 3이 됩니다.
시간 및 공간 복잡도
시간 복잡도: O(n) — 문자열을 한 번만 순회하므로 입력 크기에 비례합니다.
공간 복잡도: O(n) — 길이 n의 dp 배열을 저장하는 데 추가 공간이 필요합니다.