[Leetcode 아주 상세한 문제풀이] 91. Decode Ways – 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 91번 문제 Decode Ways 다.

우선 문제를 살펴보자.

 

리트코드 91번 문제 Decode Ways 링크

Decode Ways - LeetCode

Decode Ways - LeetCode

 

 

A message containing letters from A-Z can be encoded into numbers using the following mapping:

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

"AAJF" with the grouping (1 1 10 6)
"KJF" with the grouping (11 10 6)
Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

Given a string s containing only digits, return the number of ways to decode it.

The test cases are generated so that the answer fits in a 32-bit integer.

Example 1:
Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

Example 2:
Input: s = "226"
Output: 3
Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Example 3:
Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").
 
Constraints:
1 <= s.length <= 100
s contains only digits and may contain leading zero(s).

 

 

문제 설명

문제를 간략히 살펴보자. 우리는 알파벳을 A=1 부터 Z=26 까지 숫서대로 encoding 할 수 있다. 같은 방식으로 주어진 숫자를 알파벳으로 decoding 할 수도 있다. 예를 들어 문제에서 주어진 것 처럼 11106이란 숫자는 (1, 1, 10, 6) 혹은 (11, 10, 6)으로 쪼갤 수 있다. 그리고각 숫자는 A, A, J, F 혹은 K, J, F로 decoding 될 수 있다. 이때 유의할 점은 (1, 11, 06)으로 decoding 될 수 없다는 뜻인데 마지막에 위치한 06에서 6은 F로 매핑되지만 0이 붙는 경우 매핑이 되지 않기 때문이다. 쉽게 말하면 6과 06은 다른 숫자로 받아들여 지기 때문이다.

이때 인풋으로 주어진 숫자로 이루어진 문자열을 decoding 할 때 그 경우수의 수를 모두 찾아내라는 것이다. 예를 들어 문제 예시 1번의 경우 "12"라는 문자열이 인풋으로 주어졌다. 이는 (1, 2) 혹은 (12)로 decoding 될 수 있다. 따라서 (1, 2)의 경우 AB, (12)의 경우 L로 decoding 되므로 2가지 경우의 수가 있음을 알 수 있다. 문제를 이해하는데 어렵지 않으니 곧바로 문제를 풀어보자.

 

 

문제 접근법

이 문제를 해결하기 위해 우리는 dynamic programming을 이용할 것이다.

인풋으로 주어진 숫자로 이루어진 문자열을 처음부터 하나씩 탐색한다.

이때 처음부터 각 문자열까지에 대해 decoding 할 수 있는 방법을 계산한다.

우리는 두 가지 경우를 다루어야 한다.

1) single-digit (1-9) decoding의 경우

2) double-digit (10-26) decoding의 경우

각 경우에 대해 decoding 경우의 수를 기록할 dp 배열을 만들어 준다.

이때 dp의 각 인덱스는 인풋으로 주어진 숫자의 처음부터 해당 인덱스(i) 까지 숫자로 decoding 할 수 있는 경우의 수를 나타낸다.

따라서 dp[0]의 경우 1이 된다. (숫자가 하나만 존재해 decoding 할게 없으므로)

그리고 dp[1]의 경우 만약 처음 문자가 0이 아닌 경우 1이 된다. (이 역시 숫자가 하나만 존재해 decoding 할게 없으므로)

dp 배열의 초기화를 마치고 나면 dp[2]에 해당하는 세번째 인덱스 (index=2)부터 하나하나 탐색을 진행한다.

위에서 설명한대로 두 가지 시나리오가 존재하는데 탐색하는 문자가 single-digit일 경우와 double-digit일 경우다.

만약 single-digit일 경우 직전까지 탐색한 경우의 수 dp[i-1]를 더해준다.

우리는 decoding 할 수 있는 '경우의 수'를 찾는 것이므로 그 직전까지 decoding 할 수 있는 경우의 수가 몇개 든 지금 탐색하는 숫자 하나가 포함되어도 경우의 수는 동일하기 때문이다.

만약 double-digit의 경우 직직전 까지 탐색한 경우의 수 dp[i-2]를 더해준다.

이 경우 두 개의 문자 (혹은 숫자)를 취해야 하기 때문이다.

이런 방식으로 모든 문자에 대해 탐색을 마치고 나면 dp 배열이 업데이트 되어 있을 것이다.

앞서 설명한대로 dp 배열의 각 인덱스는 해당 인덱스에 해당하는 인풋 문자까지로 decode할 수 있는 경우의 수다.

이 문제에서는 입력받은 전체 문자에 대한 decoding 경우의 수를 물어보고 있다.

따라서 dp 배열의 마지막 인덱스 (=입력받은 문자열 길이)에 해당하는 값을 리턴하면 된다.

이제 코드로 한 번 살펴보자.

 

 

문제 풀이 코드

def num_decodings(s: str) -> int:
    if not s or s[0] == '0':
        return 0
 
    # dp[i] will store the number of ways to decode s[:i]
    dp = [0] * (len(s) + 1)
    dp[0] = 1  # Base case: empty string
    dp[1] = 1  # Base case: single character (not '0')
 
    for i in range(2, len(s) + 1):
        # Single digit decoding
        if s[i-1] != '0':
            dp[i] += dp[i-1]
 
        # Double digit decoding
        two_digit = int(s[i-2:i])
        if 10 <= two_digit <= 26:
            dp[i] += dp[i-2]
 
    return dp[len(s)]
 
# Test cases
print(num_decodings("12"))  # Output: 2
print(num_decodings("226")) # Output: 3
print(num_decodings("06"))  # Output: 0
 

 

91.&nbsp;Decode Ways