Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 풀어보는 디코드 방법의 수 II: '*' 와일드카드가 포함된 문자열 디코딩

문제 개요

A부터 Z까지의 알파벳으로 이루어진 메시지가 다음과 같은 규칙으로 숫자에 매핑되어 인코딩되었다고 가정해 보겠습니다.

'A' → 1, 'B' → 2, ... , 'Z' → 26

여기서 중요한 점은 인코딩된 문자열에 특수 문자 *(와일드카드)가 포함될 수 있다는 것입니다. 이 문자는 1부터 9까지의 어떤 숫자로든 해석될 수 있습니다. 따라서 숫자와 *가 섞여 있는 인코딩된 메시지가 주어졌을 때, 이를 디코딩할 수 있는 총 경우의 수를 구해야 합니다.

결괏값이 매우 커질 수 있으므로, 최종 답은 10⁹ + 7(1,000,000,007)로 나눈 나머지를 사용합니다. 예를 들어 입력이 * 하나뿐이라면, 이는 1부터 9까지의 숫자(A~I)로 해석될 수 있으므로 가능한 경우의 수는 총 9가지입니다.

해결 전략: 동적 프로그래밍(DP)

이 문제는 각 위치에서 한 자리 또는 두 자리 숫자로 디코딩하는 경우를 누적해 나가는 DP 방식으로 효율적으로 해결할 수 있습니다. 알고리즘의 핵심 단계는 다음과 같습니다.

1. 유틸리티 함수 정의

  • add(a, b): ((a mod m) + (b mod m)) mod m 을 반환합니다.
  • mul(a, b): ((a mod m) × (b mod m)) mod m 을 반환합니다.

2. 초기화

  • n := 문자열 s의 길이
  • 크기가 n+1인 배열 dp 선언 후 dp[0] := 1로 설정
  • s[0]이 '0'이면 어떤 문자로도 매핑되지 않으므로 0을 반환합니다.
  • dp[1] := s[0]이 '*'이면 9, 그렇지 않으면 1

3. 반복 처리 (i = 2부터 n까지)

  • first := s[i-2], second := s[i-1]로 설정합니다.
  • second가 '*'인 경우: 한 자리 숫자로 9가지 해석이 가능하므로 dp[i] += mul(9, dp[i-1])
  • second가 '0'보다 큰 경우: 해당 숫자를 그대로 하나의 문자로 해석하므로 dp[i] += dp[i-1]

이어서 두 자리 조합의 경우를 살펴봅니다.

  • first가 '*'인 경우:
    • second도 '*'라면: 11~19(9가지)와 21~26(6가지)의 합인 15가지가 가능하므로 dp[i] += mul(15, dp[i-2])
    • second가 '6' 이하라면: first가 1 또는 2 어느 쪽이든 유효하므로 dp[i] += mul(2, dp[i-2])
    • second가 '7'~'9'라면: first는 1만 가능하므로 dp[i] += mul(1, dp[i-2])
  • first가 '1' 또는 '2'인 경우:
    • second가 '*'라면: first가 '1'이면 11~19의 9가지(dp[i] += mul(9, dp[i-2])), first가 '2'이면 21~26의 6가지(dp[i] += mul(6, dp[i-2]))
    • second가 일반 숫자이고 (first - '0')×10 + (second - '0') ≤ 26이라면: dp[i] += dp[i-2]

4. 결과 반환

모든 위치를 처리한 후 최종적으로 dp[n]을 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;
class Solution {
public:
    lli add(lli a, lli b){
        return ((a % m) + (b % m)) % m;
    }
    lli mul(lli a, lli b){
        return ((a % m) * (b % m)) % m;
    }
    int numDecodings(string s) {
        int n = s.size();
        vector <int> dp(n + 1);
        dp[0] = 1;
        if(s[0] == '0') return 0;
        dp[1] = s[0] == '*' ? 9 : 1;
        for(int i = 2; i <= n; i++){
            char first = s[i - 2];
            char second = s[i - 1];
            if(second == '*'){
                dp[i] = add(dp[i], mul(9, dp[i - 1]));
            }else if(second > '0'){
                dp[i] = dp[i - 1];
            }
            if(first == '*'){
                if(second == '*'){
                    dp[i] = add(dp[i], mul(15, dp[i - 2]));
                }else if (second <= '6'){
                    dp[i] = add(dp[i], mul(2, dp[i - 2]));
                }else{
                    dp[i] = add(dp[i], mul(1, dp[i - 2]));
                }
            }else if(first == '1' || first == '2'){
                if(second == '*'){
                    if(first == '1'){
                        dp[i] = add(dp[i], mul(9, dp[i - 2]));
                    }else if(first == '2'){
                        dp[i] = add(dp[i], mul(6, dp[i - 2]));
                    }
                }else if((first - '0') * 10 + (second - '0') <= 26){
                    dp[i] = add(dp[i], dp[i - 2]);
                }
            }
        }
        return dp[n];
    }
};
main(){
    Solution ob;
    cout << (ob.numDecodings("2*"));
}

실행 결과 확인

입력

"2*"

출력

15

입력 "2*"의 결과가 15가 되는 이유는 다음과 같습니다. 첫째, '2'를 B로 디코딩하고 '*'를 A~I 중 하나로 해석하는 경우가 9가지입니다. 둘째, '2*'를 두 자리 숫자로 묶어 해석하는 경우 21~26까지만 유효하므로 6가지입니다. 따라서 9 + 6 = 15가지의 디코딩 방법이 존재합니다.

이처럼 DP 배열을 활용하면 각 자릿수에서 발생할 수 있는 해석의 수를 체계적으로 누적하여, 와일드카드가 포함된 복잡한 문자열도 O(n) 시간 복잡도 안에 효율적으로 처리할 수 있습니다.