LeetCode 91(Decode Ways, Python)

1. 문제 링크 

• https://leetcode.com/problems/decode-ways/description/

Decode Ways - LeetCode

2. 문제 설명

• 주어진 숫자 문자열을 알파벳으로 디코딩하는 방법의 수를 찾는 문제.
• 여기서 각 알파벳 A-Z는 1부터 26까지의 숫자에 대응되며, 디코딩을 할 때 숫자들을 그룹화하여 디코딩해야 함.
• 이 때 디코딩 할 수 없는 경우도 있는데 예를들어, '06'은 F에 맵핑된 '6'과 다른 값이므로 유효하지 않음
• 또한 문자열 맨 앞에 '0'이 등장하면, '0'에 대응되는 알파벳이 없기 때문에 유효하지 않음.
• 예시1) s= '12'이면 'AB'인 (1 2), 'L'인 (12)로 decode될 수 있으므로, 경우의 수가 2가지로 2를 반환
• 예시2) s= '226'이면 'BZ'인 (2 26), 'VF'인 (22 6), 'BBF'인 (2 2 6)으로 decode될 수 있으므로 경우의 수 3을 반환한다.

3. 처음 풀이

• 처음에는 backtracking을 사용하여 문제를 풀고자했다. → 하지만, timeout으로 submit 실패. 
• 아래 코드처럼
  • s[i]가 1보다 크면, path에 append하고, backtrack한 뒤, 다시 path를 pop하고
  • s[i:i+2]가 10보다 크고 26보다 작거나 같으면, path에 append하고, backtrack 한 뒤, 다시 path를 pop하였고, 
  • 마지막으로, path에 있는 문자열의 총 길이가 len(s)와 동일해질 때, output에 path를 append하여 return하도록 코드를 작성했다.
• 이렇게 하면, 모든 경우의 수가 output에 적재가 되어, 이의 length를 반환하도록 코드를 짰는데,
• 이는 처음부터 모든 경우의 수를 다 찾아야하기 때문에, 긴 문자열에서는 계속 timeout을 내뱉었고 dynamic programming을 활용해야겠다는 생각은 들었으나, 도저히 떠오르진 않았고, 결국 제로_콜라 한테 구두로 로직 설명을 들었다. 

class Solution:
    def numDecodings(self, s: str) -> int:

        def backtrack(path,start):
            
            if len(''.join(path)) == len(s):
                output.append(1)
                return
            
            for i in range(start, len(s)):
                if len(''.join(path)) != len(s[:i]):
                    break 
                if int(s[i]) >= 1:
                    path.append(s[i])
                    backtrack(path,i+1)
                    path.pop()
                if i < len(s) and int(s[i:i+2]) >= 10 and int(s[i:i+2]) <= 26:
                    path.append(s[i:i+2])
                    backtrack(path,i+2)
                    path.pop()

        output = []
        backtrack([],0)

        return len(output)

 

4. 다른 풀이 

• "1232"에 대한 경우의 수를 구한다고 해보자. 이 때 각 자리수까지의 상황을 생각해보면
  
  • 1의자리(1): 1은 mapping가능하므로 경우의 수가 1이다.
  • ~2의자리(12): 12는 1,2 와 12로 나눌 수 있으므로 경우의 수가 2이다.
  • ~3의자리(123): 이 때 12/3과 1/23으로 분해를 해서 생각해보면
    • 12/3: 3은 맵핑 가능하므로, 12의 경우의 수 2와 동일하다고 할 수 있고,
    • 1/23에서 23또한 맵핑 가능하므로, 1의 경우의 수인 1과 동일하여
    • 총 3가지 경우의 수가 존재한다고 볼 수 있다. 
  • ~4의자리(1232): 이것 또한 123/2와 12/32로 분해해서 생각할 수 있는데,
    • 123/2에서 2는 맵핑 가능하므로, 123의 경우의 수인 3과 동일하며,
    • 12/32에서 32는 26보다 큰 숫자이기 때문에 맵핑이 불가하여 경우의 수가 0이된다.
    • 즉 3+0으로 총 3가지 경우의수가 존재한다.
  • 최종적으로 4의자리까지 도달했을 때 3가지 경우의 수가 됨을 알 수 있다. 
• 이를 일반화해보면? 
  • 우선 예외 처리
    • 만약 s[0]이 0이라면, 뒤는 볼 필요도 없으므로 0을 반환한다.
    • 이를 제외하고 len(s)가 1이라면 경우의 수는 1가지 뿐이므로 1을 반환한다.
  • for문을 돌리면서,
    • 본인 자리(1자리수)가 0이 아니라면, 바로 직전의 경우의 수(a)를 가져오고, 
    • 본인과 바로 앞자리(2자리수)가 0이 아니고, 26보다 작다면, 직직전의 경우의 수(b)를 가져온 뒤, 
    • a+b한 값을 리스트에 append해주고, 최종 리스트의 가장 마지막 element를 반환하게 되면, 최종 경우의 수가 나온다.
• 코드로 작성하면 아래와 같다. 

class Solution:
    def numDecodings(self, s: str) -> int:

        if int(s[0]) == 0:
            return 0

        if len(s) ==1:
            return 1 

        if int(s[0:2]) <= 26:
            result = [1]
        else:
            result = [0]

        for i in range(len(s)):
            if i == 0:
                result.append(1)
            else:
                temp = 0
                if int(s[i]) != 0:
                    temp += result[-1]
                if int(s[i-1]) != 0 and int(s[i-1:i+1]) <= 26:
                    temp += result[-2]
                result.append(temp)

        return result[-1]

• 아래는 solution에 있는 코드로, 좀 더 깔끔하게 짠 코드이다.
  • 1자리수 digits와 2자리수 digits로 나눈 뒤에, 
    • 1자리수 digits의 경우 0이 아니면, 이전 값을 가져오고 
    • 2자리수 digits의 경우 10과 26 사이에 있으면, 두번째 이전 값을 가져와서 더해준다. 

class Solution:
    def numDecodings(self, s: str) -> int:
        if not s or s[0] == '0':
            return 0

        n = len(s)
        dp = [0] * (n + 1)
        dp[0] = 1
        dp[1] = 1

        for i in range(2, n + 1):
            one_digit = int(s[i - 1])
            two_digits = int(s[i - 2:i])

            if one_digit != 0:
                dp[i] += dp[i - 1]

            if 10 <= two_digits <= 26:
                dp[i] += dp[i - 2]

        return dp[n]

5. 배운 점

• Dynamic Programming으로 모든 것을 처음부터 다시 경우의 수를 계산하지 않고, 직전의 누적 정보를 가져와서 풀 수 있는 방법을 고민해볼 필요가 있겠다.