[Leetcode] 91. Decode Ways

Identifying the Problem

주어진 숫자 문자열 s에서 만들 수 있는 알파벳 조합의 개수를 구한다.

1	A
2	B
26	Z

01은 1이 아니므로 알파벳 취급하지 않는다.

 

예를 들어

s = 11106 이라면

1/1/1/0/6 X

11/1/0/6 X

1/11/0/6 X

1/1/10/6 -> AAJF

1/1/1/06 X

11/10/6 -> KJF

1/11/06 X

이므로 정답은 2가 된다.

Organizing thoughts

생각해 볼 점은 문자를 1개 또는 2개 단위로 검사하고

1개 단위로 검사할 때는 문자가 0이면 안 된다.

2개 단위로 검사할 때는 두 문자가 10과 26 사이의 값이어야 한다.

 

그렇다면 s를 1과 2로 자연수 분할 한 모든 경우의 수대로 구하면 될 것 같다.

하지만, 1/1/1/0/6 이 안 되는 것을 이미 알고 있는 상황에서,

11/1/0/6 을 또 검사할 필요는 없는 것 같다.

 

이럴 때 생각나는 것이 DP이다.

1부터 11106까지 결과를 저장해야 하나? 이거는 아닌 듯하다.

s[0] ~ s[n-1] 까지 결과를 저장하는 것이 올바른 접근 방법인 것 같다.

 

1은 0이 아니니 1개가 만들어진다.

dp[0]은 1이 된다.

 

11은 1/ 에 '1'이 추가된 것 또는 null/ 에 '11'이 추가된 것이므로

1개 단위는 1이고 dp[0]과 같다.

2개 단위는 null/ 에 '11'이 추가된 것이므로

dp[1]은 dp[0] + dp[-1]개가 된다. (일단은 dp[-1] = 1이 있다고 치자)

 

111은 1/1 에 '1'이 추가된 것 또는 1/ 에 '11'이 추가된 것이므로

1개 단위는 1이고 dp[1]과 같다.

2개 단위는 '1' 에 '11'이 추가된 것이므로

dp[2]은 dp[1] + dp[0]개가 된다.

 

111은 1/1 에 '1'이 추가된 것 또는 1/ 에 '11'이 추가된 것이므로

1개 단위는 1이고 dp[1]과 같다.

2개 단위는 '1' 에 '11'이 추가된 것이므로

dp[2]은 dp[1] + dp[0]개가 된다. 

 

여기서 중요하다.

 

1110은 1/1/1 에 '0'이 추가된 것 또는 1/1 에 '10'이 추가된 것이므로

1개 단위는 '0'이 추가됐기에 불가능하고,

2개 단위는 '1/1' 에 '11'이 추가 된 것이므로

dp[3]은 dp[1] 개가 된다.

 

11106은 1/1/1/0 에 '6'이 추가된 것 또는 1/1/1 에 '06'이 추가된 것이므로

1개 단위는 이전과 같고, 2개 단위는 '1/1/1' 에 '06'이 추가된 것은 불가능하므로

dp[4]은 dp[3] 개가 된다. 

 

최종 dp는 [1,2,3,2,2] 이 된다.

 

그렇다면 초기값은 어떻게 설정할까?

아까 dp[-1] = 1이 있었다고 가정했다. 

하지만 index가 -1이 되는 것은 불가능하기 때문에

dp의 길이를 n+1로 선언하고, dp[n]에 1을 대입 후 위 방식을 거꾸로 진행하면 된다.

따라서 초기값은 dp[n] = 1만 설정하고,

dp[n-1] 을 탐색할 때에는 두 자리 단위 검사를 패스하게 조건을 맞추어준다.

 

 

 

Sourcecode

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector<int> dp(n+1,0);
        //size+1로 dp를 선언하는 이유는 처음 1자리 수 검사를 할 때,
        //끝 자리가 0인지 아닌지에 따라 초기값이 바뀌기에
        //dp[n]을 1로 설정해 dp[n-1]에서 1을 끌고 가는지 아닌지 정한다.
        
        dp[n] = 1;
        
        for(int i = n-1; i>=0; i--)
        {
            if(s[i] != '0') //한 자리 단위 검사
                dp[i] += dp[i+1];
            if(i<n-1 && (s[i] == '1' || s[i] == '2' && s[i+1] <= '6'))
                dp[i] += dp[i+2]; //두 자리 단위 검사
            
        }
        return dp[0];
    }
};