문제 개요
알파벳과 숫자가 다음과 같이 매핑되어 있다고 가정해 보겠습니다. 'a' = 1, 'b' = 2, ..., 'z' = 26. 이때 인코딩된 메시지 문자열이 주어지면, 이 메시지를 디코딩할 수 있는 방법이 총 몇 가지인지 계산해야 합니다.
예를 들어, 입력이 message = "222"라면 출력은 3이 됩니다. 이 메시지는 bbb, bv, vb의 세 가지 방식으로 디코딩할 수 있기 때문입니다.
해결 접근 방식
이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 각 위치까지의 디코딩 가능한 경우의 수를 저장하는 메모이제이션(memoization) 배열을 사용합니다.
다음 단계에 따라 문제를 해결합니다:
- 메시지 길이 + 1 크기의 0으로 초기화된 리스트 memo를 생성합니다.
- memo[0] := 1 로 설정합니다.
- message[0]이 "0"이 아니면 memo[1] := 1, 그렇지 않으면 0으로 설정합니다.
- i가 2부터 메시지 길이까지일 때 반복합니다:
- n1 := message[i-1:i] 의 숫자 값
- n2 := message[i-2:i] 의 숫자 값
- n1_valid := n1 > 0 일 때 참
- n2_valid := n2 > 9 이고 n2 < 27 일 때 참
- n1_valid가 참이면 memo[i] := memo[i] + memo[i-1]
- n2_valid가 참이면 memo[i] := memo[i] + memo[i-2]
- memo 리스트의 마지막 요소를 반환합니다.
여기서 핵심 아이디어는 두 가지 경우를 고려하는 것입니다. 한 자리 숫자(1~9)로 해석하는 경우와 두 자리 숫자(10~26)로 해석하는 경우입니다. "0"으로 시작하는 숫자는 유효하지 않으므로 제외됩니다.
구현 예제
class Solution: def solve(self, message): memo = [0 for i in range(len(message)+1)] memo[0] = 1 memo[1] = 1 if message[0]!="0" else 0 for i in range(2,len(message)+1): n1 = int(message[i-1:i]) n2 = int(message[i-2:i]) n1_valid= n1>0 n2_valid= n2>9 and n2<27 if n1_valid: memo[i]+=memo[i-1] if n2_valid: memo[i]+=memo[i-2] return memo[-1] ob = Solution() message = "2223" print(ob.solve(message))
입력
"2223"
출력
5
코드 설명
입력 "2223"의 경우 결과는 5입니다. 이는 다섯 가지 방식으로 디코딩될 수 있기 때문입니다: bbv, bbf, vbv, vbf, vvf (여기서 f = 6).
동작 원리를 살펴보면:
- 한 자리 검증(n1_valid): 현재 위치의 한 자리 숫자가 1~9 사이라면, 해당 자리 하나만큼 앞선 위치의 누적 경우의 수(memo[i-1])를 더합니다.
- 두 자리 검증(n2_valid): 직전 두 자리 숫자가 10~26 사이라면, 두 자리 앞선 위치의 누적 경우의 수(memo[i-2])를 더합니다.
이렇게 하면 시간 복잡도 O(n), 공간 복잡도 O(n)으로 문제를 해결할 수 있으며, 재귀 방식보다 훨씬 효율적입니다.