[LeetCode] 91. Decode Ways

문제 출처: https://leetcode.com/problems/decode-ways/

Decode Ways - LeetCode

---

문제

A-Z 의 문자가 포함된 메시지가 다음과 같은 매핑을 사용하여 인코딩할 수 있다.

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

인코딩 된 메시지를 디코딩하기 위해, 모든 숫자는 그룹화한 다음 위 매핑 표의 역으로 문자로 매핑되어야 한다(다양한 방법이 존재할 수 있음). 예를 들어, "11106"은 아래와 같이 매핑될 수 있다:

• (1 1 10 6)으로 그룹화되어 "AAJF"로 디코딩
• (11 10 6)으로 그룹화 되어 "KJF"로 디코딩

 

그룹 (1 11 06)은 유효하지 않은 그룹인데, "06"은 "6"과는 달라 "F" 문자로 매핑할 수 없기 때문이다.

 

오직 숫자로 구성된 문자열 s 가 주어지면, 그것을 디코딩할 수 있는 방법의 수를 반환하라.

 

답은 32비트 정수임을 보장한다.

 

예제

Input: s = "226"
Output: 3

Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Input: s = "0"
Output: 0

Explanation: There is no character that is mapped to a number starting with 0.
The only valid mappings with 0 are 'J' -> "10" and 'T' -> "20", neither of which start with 0.
Hence, there are no valid ways to decode this since all digits need to be mapped.

---

풀이

주어진 s에서 제일 앞쪽(왼쪽) 문자부터 한 개의 문자를 하나의 그룹으로 보는 경우와 두 개의 문자를 하나의 그룹으로 보는 경우를 나누어서 본다. 만약 s = "226" 이라면, 아래의 그림과 같은 방식으로 가능한 모든 그룹의 패턴을 찾아낼 수 있다.

위 그림에서 노란 박스는 그룹을 만들어야 하는 문자열을 의미하고, 파란 박스는 하나의 그룹을 의미한다. 즉, "226"이라는 인코딩 값은 (2 2 6)="BBF", (2 26)="BZ", (22 6)="VF"와 같이 디코딩될 수 있다.

 

위 그림의 과정을 코드로 구현하기 위해 재귀 방식을 사용할 수 있다.

 

재귀를 사용하기 위해서 1. 종료 조건, 2. 재귀 호출 조건 에 대해 고려해야 한다.

• 종료 조건
  • 더 이상 탐색해야할 문자가 없음: 모든 숫자를 그룹화했음
  • 탐색 문자의 시작이 '0'인 경우('0'으로 시작하는 케이스는 존재 X): 그룹화 불가능

• 재귀 호출 조건
  • 나눈 숫자가 범위(1~26) 내에 있는 경우

var numDecodings = function(s) {
    function findSubDecoding(s, idx) {
        if (s[idx] == '0') { return 0; }
        if (idx >= s.length) { return 1; }
        
        const selectOne = findSubDecoding(s, idx+1);
        const selectTwo = (idx < s.length-1 && Number(s.substring(idx, idx+2)) <= 26) ? findSubDecoding(s, idx+2) : 0;
        
        return selectOne + selectTwo;
    }
    
    return findSubDecoding(s, 0);
};

위 코드는 문자 s와 아직 그룹화되지 않은 시작 인덱스 idx를 입력받아 동작하는 재귀 함수이다. selectOne 변수가 하나의 숫자를 하나의 그룹으로 지정했을 때의 케이스를 나타내고, selectTwo 변수가 두 개의 숫자를 하나의 그룹으로 지정했을 때를 나타낸다.

 

selectTwo에서 재귀를 호출하는 조건을 살펴보면,

• 하나의 그룹으로 보고자하는 숫자가 26보다 작은가?
• idx < s.length-1 인가?

두 번째 조건은 뭐지? 라고 생각할 수 있는데, 이 조건의 의미를 파악하기 위해 s = "226" 예제를 다시 살펴보자.

위 그림에서 빨간 박스로 표시해놓은 것을 보면, 22를 하나의 그룹으로 보고 난 후에 남는 문자가 6밖에 없다는 것을 볼 수 있다. 이 경우 두 개의 문자를 선택하는 경우란 존재할 수가 없다. 바로 이러한 케이스를 두 번째 조건인 idx < s.length-1 으로 걸러내는 것이다.

 

현재 알고리즘을 DP를 이용하여 최적화할 수 있다. DP에 저장할 값은 s의 i인덱스부터 끝 문자까지 그룹화할 때, 가능한 그룹의 개수이다. 위의 "226"인 간단한 경우만 보아도 인덱스 2인 위치에서 대한 연산(숫자 6만 노란 박스로 쳐진 경우)이 2번 반복되는 것을 볼 수 있다. s의 길이가 길어질수록 이렇게 중복되는 연산이 많을 것이고 이를 저장하는 것으로 연산의 횟수를 줄이고자 하는 것이다.

var numDecodings = function(s) {
    const memo = Array(s.length).fill(null);
    
    function backtracking(s, idx) {
        if (s[idx] == '0') { memo[idx] = 0; }
        if (memo[idx] != null) { return memo[idx]; }
        if (idx >= s.length) { return 1; }
        
        const selectOne = backtracking(s, idx+1);
        const selectTwo = (idx < s.length-1 && Number(s.substring(idx, idx+2)) <= 26) ? backtracking(s, idx+2) : 0;
        
        memo[idx] += (selectOne + selectTwo)
        
        return memo[idx];
    }
    
    backtracking(s, 0, "");
    
    return memo[0];
};

 

Github: 91.js

GitHub - opwe37/Algorithm-Study