Decode Ways

Decode Ways

문제 내용

대문자 A부터 Z까지를 1부터 26까지의 숫자와 대응시켰을 때

주어진 숫자로 만들어 낼 수 있는 문자의 갯수는 몇개인가?

 

접근 방법

우선 Brute force 접근의 경우는 모든 경우를 분기 시키는 것이 가능하다.

만약에 '112'가 주어졌다고 하면

'aab','ai','kb' 이렇게 3개의 선택을 할 수 있다. 이 선택의 순서를 dfs방식으로 하게 되면, 최악의 경우 '11111111' <- 이런경우 매 순간 1이냐 11이냐 2개의 선택이 가능하다.

대략적인 시각복잡도는 $ O(2^n) $ 이 되게 된다. 그러나 이것을 memorization하면 한번에 한 Path만 지나게 됨으로 $ O(N length) $라고 한다. 해답으로 나온거니까 맞을 것이라고 생각한다.

leetcode 해답을 보니 위의 방법이 쉽게 문제 접근하기 좋은거 같다.

나는 다른 방식으로 접근을 했다.

 

패턴 찾기

해당 문제의 pattern을 찾기 위해서 몇가지 내용을 확인 했다.

'11111026' 이 주어졌을 때를 따라가 보자.

0이 아닌 한자리 수일 경우 무조건 1회가 답이 된다.

11은 AA와 K 두가지 경우가 생기게 된다. 답은 2이다.

111은 AAA, KA, AK이렇게 3가지 경우의 수가 나오게 되는데, 무언가 위의 1과 11사이에 연관성을 발견 할 수 있다.

111 중 111 이 확정된 경우 추가된 1 A를 붙혀서 완성한다. 

만약 앞의 1과 합쳐서 1만 확정시키고 2가지를 자리를 합치면 i-2 자리수의 A와 확정 K를 합쳐서 1 가지수가 된다.

이 두가지를 더해보면 3이 된다.

벌서 무언가 패턴이 보이는데 조금더 확인해 보자.

이경우도 i-1의 결과값에 A를 확정지은 갯수와 i-2에 결과값에 2자리 sum인 K를 확정 지은 수로 나타낼 수 있다.

이경우도 마찬가지다.

이를 통해서 다음과 같은 공식 유도가 가능하다는 것을 유추 할 수 있다.

• dp[n] = dp[n-1] + dp[n-2]

그럼 만약에 0인 경우는 어떻게 해야할까?

0인 경우는 dp[n-1]을 선택할 수가 없다. 그 이유는 0이 혼자서 선택될 수 없기 때문이다.

• dp[n] = dp[n-2] (현재 값이 0인경우)

그럼 앞자리가 0인 경우는 어떨까?

2의 앞이 0인경우는 2자리를 합쳐서 하나로 만들 수 없음으로 dp[n-2]를 계산 할 수 없다.

이것은 다른 말로 바꿔 말하자면 2자리를 합쳐서 0보다 크고 26보다 작은 값이 아니면 2자리로써 사용이 불가함으로 dp[n-2]는 사용할 수 없다.

• dp[n] = dp[n-1] (2자리의 값이 0 < 2자리 < 27 이 아닌 경우)

 

 

마지막으로 6을 넣어서 dp[n-1]과 dp[n-2]를 선택 가능한 경우에는 두개의 가지수를 sum하면 답이 된다.

 

이 로직을 정리하면 다음과 같이 말할 수 있다.

• 현재의 값이 한자리로써 사용할 수 있는 경우 dp[n-1]의 가짓수를 사용할 수 있다.
• 현재의 값과 바로 앞자리의 값이 2자리로써 사용할 수 있는 경우 dp[n-2]의 가짓수를 사용할 수 있다.

 

프로그램

이 패턴을 바탕으로 다음과 같이 프로그램을 짤 수 있다.

var numDecodings = function(s) {
    let dp = new Array(s.length).fill(0);
    dp[0] = s.charAt(0) === '0'? 0 : 1;
    
    for(let i = 1; i < s.length; i++){
        let oneStep = dp[i-1]?? 0;
        let twoStep = dp[i-2]?? 1;
        
        if(s.charAt(i) === '0'){
            oneStep = 0;
        }
        
        const twoCharsInt = parseInt(s.charAt(i-1) + s.charAt(i));
        
        if(s.charAt(i-1) === '0' || 26 < twoCharsInt){
            twoStep = 0;
        }
        dp[i] = oneStep + twoStep;
    }
    // console.log(dp);
    return dp[dp.length-1];
};

위에서는 dp로 space complexity를 $ O(N) $을 사용했지만, 실질적으로 사용하는 메모리는 2개임으로 이것을 아래와 같이 최적화 가능하다.

var numDecodings = function(s) {
    let dp = new Array(s.length).fill(0);
    let oneStep = s.charAt(0) === '0'? 0 : 1;
    let twoStep = 1; 
    let result = oneStep;
    
    for(let i = 1; i < s.length; i++){     
        result = 0;
        
        if(! (s.charAt(i) === '0')){
            result += oneStep;
        }
        
        const twoCharsInt = parseInt(s.charAt(i-1) + s.charAt(i));
        
        if(!(s.charAt(i-1) === '0' || 26 < twoCharsInt)){
            result += twoStep;
        }
        twoStep = oneStep;
        oneStep = result;
    }
    return result;
};

time complexity는 $ O(N) $ 이 된다.