C++에서 주어진 숫자 시퀀스의 가능한 디코딩 개수 구하기

숫자 시퀀스를 나타내는 문자열이 하나 주어집니다. 각 숫자는 1부터 26까지의 영어 알파벳으로 디코딩할 수 있습니다. 즉, 1은 'A', 2는 'B'처럼 대응되며 26은 'Z'가 됩니다. 이때 목표는 주어진 숫자 시퀀스로 만들 수 있는 모든 디코딩의 개수를 구하는 것입니다. 예를 들어 시퀀스가 '123'이라면 가능한 디코딩은 'ABC'(1-2-3), 'LC'(12-3), 'AW'(1-23)의 세 가지이므로 정답은 3입니다.

예제로 이해하기

입력 − str[]="1532"

출력 − 주어진 숫자 시퀀스의 가능한 디코딩 개수 − 2

설명 − 가능한 디코딩은 AECB(1-5-3-2)와 OCB(15-3-2)입니다.

입력 − str[]="216"

출력 − 주어진 숫자 시퀀스의 가능한 디코딩 개수 − 3

설명 − 가능한 디코딩은 "BAF"(2-1-6), "UF"(21-6), "BP"(2-16)입니다.

프로그램에서 사용한 접근 방식

이 문제는 재귀(recursion) 방식으로 해결할 수 있습니다. 문자열의 일부분을 재귀 함수에 계속 전달하면서 경우의 수를 누적해 가는 구조입니다.

먼저 마지막 숫자가 '0'이 아닌지 확인합니다. '0'이 아니라면 그 숫자 하나를 알파벳 하나로 디코딩할 수 있으므로, 앞부분(0 ~ length-1)에 대한 재귀 호출 결과를 카운트에 반영합니다. 다음으로 마지막 두 자리가 1 이상 26 이하의 수를 이루는지 확인합니다. 조건을 만족한다면 두 자리를 하나의 알파벳으로 디코딩할 수 있으므로, 앞부분(0 ~ length-2)에 대한 재귀 호출 결과를 추가로 더합니다.

입력은 문자열 str[]로 받습니다.
함수 decode_digit_seq(char *str, int length)는 문자열과 그 길이를 인자로 받아 가능한 디코딩의 개수를 반환합니다.
길이가 0이면 1을 반환합니다. (빈 문자열도 한 가지 디코딩으로 취급)
길이가 1이면 1을 반환합니다.
마지막 한 자리 문자가 '0'이 아니면 count = decode_digit_seq(str, length-1)
뒤에서 두 번째 문자가 '1'이면 마지막 두 자리는 10~19(J~S) 범위이므로 count = count + decode_digit_seq(str, length-2)
뒤에서 두 번째 문자가 '2'이고 마지막 문자가 '7' 미만이면 마지막 두 자리는 20~26(T~Z) 범위이므로 count = count + decode_digit_seq(str, length-2)
이렇게 하면 모든 경우가 처리됩니다.
모든 재귀 호출이 끝나면 count를 결과로 반환합니다.

예시 코드

#include <iostream>
#include <cstring>
using namespace std;
int decode_digit_seq(char *str, int length){
    int count = 0;
    if(length == 0){
        return 1;
    }
    if(length == 1){
        return 1;
    }
    if(str[0] == '0'){
        return 0;
    }
    if(str[length-1] > '0'){
        count = decode_digit_seq(str, length-1);
    }
    if(str[length-2] == '1'){
        count = count + decode_digit_seq(str, length-2);
    }
    if(str[length-2] == '2' && str[length-1] < '7'){
        count = count + decode_digit_seq(str, length-2);
    }
    return count;
}
int main(){
    char str[] = "7651";
    int length = strlen(str);
    cout<<"주어진 숫자 시퀀스의 가능한 디코딩 개수: "<< decode_digit_seq(str, length);
    return 0;
}

출력

위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −

주어진 숫자 시퀀스의 가능한 디코딩 개수: 1

문자열 "7651"의 경우 76, 65, 51은 모두 26을 초과하므로 두 자리 묶음으로는 디코딩할 수 없습니다. 따라서 7(G)-6(F)-5(E)-1(A)로만 읽을 수 있기 때문에 결과는 1이 됩니다.

참고: 시간 복잡도

위 재귀 풀이는 최악의 경우 지수 시간인 O(2^n)이 걸릴 수 있습니다. 이미 계산한 부분 문제의 결과를 배열에 저장해 두는 메모이제이션(memoization) 또는 동적 계획법(DP)을 적용하면 O(n) 시간에 효율적으로 해결할 수 있습니다.