[ leetcode 문제풀이 ] Decode Ways

 

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

Decode Ways - LeetCode

(Decode Ways 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

 

< Decode Ways 문제 설명 >

 

Decode Ways 문제는 다음과 같다.

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.

 

A-Z 알파벳에 대해 숫자 1~26으로 암호화한 message를 받아 가능한 decode 방법의 수를 리턴하여라.

 

다음 세 가지 출력 예시가 주어졌다.

주어진 제한 조건은 1 ≤ s.length ≤ 100과 s는 숫자로만 구성되어 있고 0으로 시작할 수 있다는 것이다.

 

 

 

---

< Decode Ways 문제 접근 >

 

이 문제를 풀기 위해서는 다음 사항들을 고려해야 한다.

문자열 s의 숫자가 decode할 수 있는지 여부를 확인해야 하며 이를 위해 1자리(1~9의 값을 갖는지)와 2자리(10~26의 값을 갖는지)로 끊어서 생각해봐야 하며, 0이 s에 포함되는 경우는 어떻게 올바른 출력이 나오도록 처리할 것인가를 생각해야 한다.

 

우선 첫 번째 문제는 부분 문제의 조각으로 나누어 간단하게 처리해줄 수 있다. s = '226'인 경우를 예로 들어보자.

cache라는 메모이제이션을 위한 배열을 default 값으로cache[0]=1이라 정의하고, 'cache[i] = s[:(i+1)]에 대해 가능한 decode의 방법 수'라고 정의하자. 그러면 s[0]=2는 B로 decode 가능하다(cache[1] = 0 + cache[0]).

s[1] = 2는 B로 decode 가능하며 s[0:2] = 22는 V로 decode 가능하다(cache[2] = cache[1] + cache[0]). 

s[2] = 6은 F로 decode 가능하며 s[1:3] = 26은 Z로 decode 가능하다(cache[3] = cache[2] + cache[1]).

 

위 예시에서 decode 가능한 방법 수를 카운팅하는 메커니즘을 살펴보면, i index 값에 대해 decode 가능 여부를 체크해 가능하면 cache[i+1] += cache[i]를 해주고 i-1 ~ i index 값에 대해 decode 가능 여부를 체크해 가능하면 cache[i+2] += cache[i]를 해준다. 

 

이와 같은 메커니즘을 코드로 나타내면 아래와 같다. (Cpp 사용)

#include <sstream>
using namespace std;

int numDecodings(string s) {
    vector<int>cache(2);
               
    if(s[0] == '0') return 0;  // 첫 원소로 0이 나오면 반드시 불가능하므로 0 리턴
    cache[0] = 1;
    if(s[0] != '0')
        cache[1] = 1;
      
    for(int i=1;i<s.size();i++){
        int temp;
        stringstream ssInt(s.substr(i-1,2));  // leetcode에서 stoi를 지원하지 않아 sstream 사용
        ssInt >> temp;
        
        if(temp < 10 || temp > 26)
            cache[(i+1)&1] = 0;
        if(s[i] != '0')
            cache[(i+1)&1] += cache[i&1];
    }
    return cache[s.size()&1];
}

cache[i+2]를 알기 위해서는 cache[i+1]과 cache[i] 정보만 알고 있으면 된다. 따라서 메모이제이션을 위해 2*sizeof(int) 만큼만 메모리를 할당해주었다. 

 

Complexity analysis를 해보면 시간복잡도는 O(n)이고 공간복잡도는 O(1)이다. Runtime으로는 3ms, Memory Usage로는 6MB의 결과를 보였다.