문제 개요
반복된 숫자를 여러 개 포함하는 숫자가 문자열 형태로 주어졌을 때, 이 숫자를 읽는(철자하는) 방법이 총 몇 가지인지 구하는 것이 목표입니다. 예를 들어 112233은 "더블 원, 더블 투, 더블 쓰리(double one, double two, double three)" 또는 "원 원 투 투 쓰리 쓰리(one one two two three three)"처럼 서로 다른 방식으로 읽을 수 있습니다.
해결의 핵심은 연속된 숫자를 확인하는 것입니다. 숫자가 "13"이라면 "원 쓰리(one three)"로 읽는 한 가지 방법만 존재합니다. 하지만 "113"이라면 "더블 원 쓰리(double one three)", "원 원 쓰리(one one three)"로 두 가지 방법이 가능합니다. 즉, 문자열에서 연속으로 이어진 같은 숫자의 개수를 그룹별로 센 뒤, 각 그룹마다 2(개수-1)를 곱해주면 전체 경우의 수를 구할 수 있습니다.
예시를 통해 자세히 살펴보겠습니다.
입력
num="11211"
출력
반복 숫자가 있는 숫자의 철자 방법 수: 4
설명
가능한 방법:
1. One one two one one
2. Double one two one one
3. One one two double one
4. Double one two double one
입력
num="2212"
출력
반복 숫자가 있는 숫자의 철자 방법 수: 2
설명
가능한 방법:
1. Two two one two
2. Double two one two
프로그램에 사용된 접근 방식
숫자를 문자열 str로 받아옵니다.
word_spell(string str) 함수는 str에 담긴 숫자를 인자로 받아 철자 표기 방법의 수를 반환합니다.
경우의 수를 누적할 변수 count를 1로 초기화합니다.
for 루프를 사용해 문자열의 각 자릿수를 순회합니다.
특정 숫자의 반복 횟수를 저장할 변수 temp를 선언하고, str[i] == str[i+1]이면 temp를 1씩 증가시킵니다.
count = count * pow(2, temp-1) 공식으로 각 그룹의 경우의 수를 곱해 누적합니다.
모든 자릿수를 확인한 후 count를 최종 결과로 반환합니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
long long int word_spell(string str){
long long int count = 1;
int len = str.length();
for (int i=0; i<len; i++){
int temp = 1;
while(i < len-1 && str[i+1] == str[i]){
temp++;
i++;
}
count = count * pow(2, temp-1);
}
return count;
}
int main(){
string str = "222211";
cout<<"Count of ways to spell a number with repeated digits are: "<<word_spell(str);
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
Count of ways to spell a number with repeated digits are: 16
결과 분석
입력 "222211"의 경우, 앞의 "2222"는 연속된 네 개의 2이므로 2(4-1) = 8가지, 뒤의 "11"은 연속된 두 개의 1이므로 2(2-1) = 2가지 방법이 있습니다. 따라서 전체 경우의 수는 8 × 2 = 16가지가 됩니다. 이처럼 각 연속 그룹을 독립적으로 계산한 뒤 곱해주면 시간 복잡도 O(n)으로 문제를 효율적으로 해결할 수 있습니다.