[LeetCode] 91. Decode Ways 풀이 및 코드

문제

문자열이 주어지면 이를 키를 이용하여 해독하는 방법의 수를 리턴하는 문제이다. 해독하기 위한 키는 다음과 같다.

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

예)

"12"는 "AB"나 "L"로 해독될 수 있다. (2가지 방법)

"123"은 "ABC"나 "LC"나 "AW"로 해독될 수 있다. (3가지 방법)

---

풀이

이번 코드는 길이는 짧으나 직관적이지는 않은 것 같다. (더 좋은 방법이 떠오르면 추후에 수정해야 겠다!)

주어진 문자열을 순회하면서

    1) 해당 인덱스(i)의 숫자가 1~9의 숫자인지 확인한다. 맞다면 i까지의 방법 개수는 i-1까지의 방법 개수와 같다. (이 문장이 이해가 가지 않는다면 예로 "89"를 생각해 보자. i가 1인 상황을 가정한다. "9"는 1~9의 숫자이므로 1번 인덱스까지의 해독 방법 개수는 0번 인덱스까지의 해독 방법 개수와 같다. 0까지의 방법 개수는 한 개이다. 따라서 "89"도 해독 방법은 1개이다.)

    2) 전 인덱스(i-1)와 해당 인덱스(i)의 숫자를 이으면 10~26 사이의 숫자가 되는지 확인한다. (∵ 01~09는 해독할 수 있는 키가 없다.) 맞다면 i까지의 방법 개수는 i-2까지의 방법 개수와 같다.  

예외 case를 처리해야 한다. 이 알고리즘에서의 예외 케이스는 1)에서는 i가 1일 때, 2)에서는 i가 2일 때 일 것이다. 그 이유는 이전까지의 방법 개수를 가져다 써야 하는데, 문자열의 앞 부분이므로 이전의 방법 개수가 없기 때문이다. 따라서 이를 해결하기 위해 앞 부분(i<2)의 방법 개수를 추가해 주었다.

---

코드

class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        cnt = [0 for _ in range(len(s)+2)]
        for i in range(len(s)+2):
            if i < 2:
                cnt[i] = 1
            else:
                if int(s[i-2]) > 0 and int(s[i-2]) <= 9:
                    cnt[i] += cnt[i-1]
                if i >= 3:
                    if int(s[i-3:i-1]) >= 10 and int(s[i-3:i-1]) <= 26:
                        cnt[i] += cnt[i-2]
        return cnt[-1]

---

리트코드 제출 결과

---

출처

leetcode.com/problems/decode-ways/