[LeetCode] 91. Decode Ways 풀이 (Java)

✔️ 오늘의 리트코드 공부 기록 – Decode Ways

---

 

문제 요약 (Decode Ways)

숫자로만 구성된 문자열 s가 주어지고, 'A'=1, 'B'=2, ..., 'Z'=26으로 매핑된다.
문자열을 디코딩할 수 있는 모든 방법의 수를 구하라.

 

문제링크: https://leetcode.com/problems/decode-ways

---

 

🤔 처음 떠올린 생각

문제를 보자마자 핵심 키워드는 “방법의 수”였다.
즉, 모든 경우를 고려해야 하는 문제라는 점이 바로 보였다.

 

하지만

• 문자 하나씩 모든 경우를 완전 탐색으로 나열한다면
• 같은 부분 문자열을 반복해서 계산하게 되고
• 결국 시간 초과가 날 것이라고 판단했다.

그래서 자연스럽게

“이미 계산한 경우의 수를 저장해두자”

 

라는 생각으로 이어졌고, DP + 메모이제이션이 가장 먼저 떠올랐다.

---

 

💡 핵심 아이디어: 재귀 전이식

재귀 함수의 의미를 먼저 정의했다.

• dfs(i) = i번째 문자부터 끝까지 디코딩 가능한 경우의 수

 

그 다음 가능한 선택지는 두 가지뿐이다.

1. 한 글자 사용: s[i] != '0' → dfs(i) += dfs(i+1)
2. 두 글자 사용: 10 <= s[i..i+1] <= 26 → dfs(i) += dfs(i+2)

즉, 결국 재귀 구조는 이렇게 단순화된다:

dfs(i) = dfs(i+1) + dfs(i+2) // 조건 만족 시

 

 

이 재귀를 그대로 1차원 DP로 변환할 수 있다.

•  dp[i] → i번째 문자부터 끝까지 디코딩 가능한 경우의 수

if s[i] != '0' → dp[i] += dp[i+1]
if 10 <= s[i..i+1] <= 26 → dp[i] += dp[i+2]

---

 

코드 (Java) - 재귀 + 메모이제이션

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        Integer[] memo = new Integer[n];
        return dfs(s, 0, memo);
    }

    private int dfs(String s, int i, Integer[] memo) {
        int n = s.length();
        if (i == n) return 1;
        if (s.charAt(i) == '0') return 0;
        if (memo[i] != null) return memo[i];

        int ans = dfs(s, i + 1, memo);
        if (i + 1 < n) {
            int twoDigit = Integer.parseInt(s.substring(i, i + 2));
            if (twoDigit >= 10 && twoDigit <= 26) ans += dfs(s, i + 2, memo);
        }

        memo[i] = ans;
        return ans;
    }
}

 

 

📈 Time / Space Complexity

• 시간: 모든 문자를 한 번씩 계산 → O(N)
• 공간: dp 배열 / 메모이제이션 → O(N)

---

 

코드2 (Java) - for 문 DP

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[n] = 1; // 빈 문자열 기준

        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) != '0') dp[i] += dp[i + 1];
            if (i + 1 < n) {
                int twoDigit = Integer.parseInt(s.substring(i, i + 2));
                if (twoDigit >= 10 && twoDigit <= 26) dp[i] += dp[i + 2];
            }
        }
        return dp[0];
    }
}

 

---

 

📝 이번 문제에서 얻은 깨달음

• “경우의 수를 구하라” → 모든 경우를 고려해야 한다
• 하지만 모든 경우를 그대로 나열하면 안 된다
• 같은 부분 문제가 반복된다면 → DP / 메모이제이션을 떠올리는 게 핵심
• 재귀로 사고 흐름을 먼저 잡고 → 그 구조를 DP로 옮기는 방식이 가장 자연스러웠다