Code › algorithm-study
LeetCode 91 - Decode Ways
문자열의 한 자리와 두 자리 해석을 재귀와 메모이제이션으로 계산한 Python 풀이
숫자로 이루어진 문자열을 알파벳으로 해석할 수 있는 경우의 수를 구하는 Medium 문제다. 현재 위치에서 한 자리를 사용하는 경우와 두 자리를 사용하는 경우로 나누면 재귀 구조가 만들어지고, 같은 위치를 반복해서 계산하지 않도록 메모이제이션을 적용했다.
문제 링크 & 설명
- 문제 링크: 91. Decode Ways
- 요약: 1부터 26까지를 A부터 Z에 대응시킬 때, 주어진 숫자 문자열을 해석할 수 있는 전체 경우의 수를 반환하는 문제다.
예를 들어 226은 2-2-6, 22-6, 2-26으로 나눌 수 있으므로 세 가지 해석이 가능하다. 다만 0은 혼자 문자로 바꿀 수 없고, 10이나 20처럼 유효한 두 자리 숫자의 일부로만 사용할 수 있다.
접근 방법
재귀 함수는 현재 읽을 위치인 idx를 상태로 사용한다. idx가 문자열 끝에 도달했다면 하나의 유효한 해석을 완성한 것이므로 1을 반환하고, 현재 문자가 0이면 그 경로는 더 진행할 수 없어 0을 반환한다.
한 자리 숫자를 사용하는 경우에는 idx + 1로 이동한다. 현재 위치부터 두 글자를 잘랐을 때 값이 10부터 26 사이라면 두 자리 숫자로도 해석할 수 있으므로 idx + 2로 이동한 결과를 더한다.
ways = self.decode(s, idx + 1, memo)
if idx + 2 <= len(s):
num = int(s[idx:idx + 2])
if 10 <= num <= 26:
ways += self.decode(s, idx + 2, memo)서로 다른 경로가 같은 idx에 도달하면 그 뒤의 경우의 수는 동일하다. memo[idx]에 결과를 저장하면 각 위치를 한 번만 계산할 수 있다.
트러블 슈팅
가장 신경 써야 하는 값은 0이었다. 현재 문자가 0인 경로를 바로 종료하지 않으면 06처럼 유효하지 않은 조각을 한 자리 숫자 0과 6으로 처리할 수 있다. 반대로 idx가 문자열 길이와 같아진 경우는 실패가 아니라 문자열 전체를 정상적으로 사용한 경우이므로 1을 반환해야 한다.
이 두 조건의 순서도 중요하다. 문자열 끝에 도달했는지 먼저 확인해야 s[idx]에 접근할 때 범위를 벗어나지 않는다.
복잡도 분석
- 시간 복잡도: O(n)
- 문자열의 각 인덱스 결과를 memo에 저장하므로 각 위치를 한 번씩 계산한다.
- 공간 복잡도: O(n)
- memo 배열과 최악의 경우 한 글자씩 내려가는 재귀 호출 스택이 필요하다.
구현 코드
from typing import List
class Solution:
def decode(self, s: str, idx: int, memo: List[int]) -> int:
if idx == len(s):
return 1
if idx > len(s):
return 0
if int(s[idx]) == 0:
return 0
if memo[idx] != -1:
return memo[idx]
ways = self.decode(s, idx + 1, memo)
if idx + 2 <= len(s):
num = int(s[idx:idx + 2])
if 10 <= num <= 26:
ways += self.decode(s, idx + 2, memo)
memo[idx] = ways
return ways
def numDecodings(self, s: str) -> int:
memo = [-1] * len(s)
return self.decode(s, 0, memo)요약 및 회고
현재 위치에서 한 자리와 두 자리 선택을 나누면 재귀식 자체는 단순하다. 실제로 경우를 가르는 조건은 0을 단독으로 사용할 수 없다는 점과 두 자리 값이 10부터 26 사이여야 한다는 점이었다. idx만으로 이후의 결과가 결정되므로 메모이제이션을 적용해 중복 호출을 선형 시간으로 줄일 수 있었다.