Decode Ways

DP문제가 조금씩 비슷한 패턴의것들은 조금 눈에 보이는거 같기도 하지만 아직 어려운거 같다. 이번 문제는 싫어요 숫자도 많길래 별로인 문제인가 하고 풀어봤는데 확실히 좀 까다로운 조건들이 꽤 있었다...숫자가 주어질때 이 숫자들이 알파벳으로 변환될수 있는 숫자면은 그 숫자를 계속해서 누적시키는게 가장 중요한 관건이었다.

그렇기때문에 확인해야 할 조건들은 두가지가 있었다.

1. 한자릿수만 봤을때 1이상 9이하인가?
2. 두자리숫자로 봤을때 10이상 26이하인가?

결국 어떤 알파벳이여도 세자리 숫자는 될수없기에 두자리까지 유심히 보는게 중요하다. 그런데 여기서 내가 가장 헤맸던거는 두번째 자리 숫자였다. 수가 두가지만 나왔을경우, 예를 들어 10일경우. 10은 1과 0으로 쪼갤수는 없다. 왜냐면 0번째 자리 수 알파벳은 없기때문이다. 그렇기때문에 답은 10하나인데 이 조건을 생각하는게 좀 까다로웠다.

일단 누적을 이어가야하기때문에 첫번째 자리수의 조건이 만족되면 바로 전에 누적된 횟수를 더해줬고 두자리 숫자가 조건을 만족하면 두번째 자리수 전에꺼를 더해줬다. DP길이를 s.length + 1을 해주었고 조건을 계속 확인해주면서 업데이트 해줬다.

여기서 배운점은 모든 DP배열 크기와 방식이 같지가 않고 문제에 떄라서 더 늘려야할때도 있다는거를 새롭게 알았다.

class Solution {
public:
    int numDecodings(string s) {
        if(s[0] == '0') return 0; 
        if(s.length() == 1) return 1; 
        vector<int> dp(s.length()+1,0); 
        dp[0] = 1;
        //dp[1] = s[1] != '0' && stoi(s.substr(0,2)) >= 11 && stoi(s.substr(0,2)) <= 26 ? dp[0] + 1 : dp[0]; 
        dp[1] = 1; 
        for(int i = 2; i <= s.length(); i++){
            int val1 = stoi(s.substr(i-1,1)); 
            int val2 = stoi(s.substr(i-2,2)); 

            if(val1 >= 1 && val1 <= 9) dp[i] += dp[i-1]; 
            if(val2 >= 10 && val2 <= 26) dp[i] += dp[i-2]; 
        }
        return dp[s.length()]; 
    }
};