문제 소개
양의 정수 하나가 주어졌다고 가정해 봅시다. 우리는 이 숫자를 영어 단어로 풀어 써야 합니다. 예를 들어 숫자 "56"이 입력으로 주어지면 출력은 "Fifty-Six"가 되어야 하며, 변환 가능한 범위는 최대 10억(Billion)까지입니다.
따라서 입력이 5678이라면 출력은 "Five Thousand Six Hundred Seventy Eight"가 됩니다.
해결 접근 방법
이 문제는 사전에 정의된 숫자 매핑 배열과 재귀 함수를 활용하면 간결하게 해결할 수 있습니다. 전체 알고리즘은 다음 단계로 진행됩니다.
1단계: 숫자 매핑 배열 정의
(영어 단어, 값) 형태의 쌍을 담은 배열 'numbers'를 값 기준 내림차순으로 정의합니다.
- {"Billion", 1000000000}
- {"Million", 1000000}
- {"Thousand", 1000}
- {"Hundred", 100}
- {"Ninety", 90}, {"Eighty", 80}, {"Seventy", 70}, {"Sixty", 60}, {"Fifty", 50}, {"Forty", 40}, {"Thirty", 30}, {"Twenty", 20}
- {"Nineteen", 19}부터 {"Ten", 10}까지의 십 단위 숫자들
- {"Nine", 9}부터 {"One", 1}까지의 한 자리 숫자들
2단계: solve() 재귀 함수 정의
- 입력값이 0이면 "Zero"를 반환합니다.
- numbers 배열의 각 요소(num)를 앞에서부터 차례대로 검사합니다. num의 값이 입력값보다 작거나 같으면 다음을 수행합니다.
- num의 값이 100 이상인 경우: result를 solve(입력값 ÷ num의 값) + " " + num의 단어로 설정합니다. 이후 입력값이 (입력값 ÷ num의 값) × num의 값보다 크다면, 나머지 부분에 대해 solve()를 재귀 호출한 결과를 공백과 함께 뒤에 덧붙입니다.
- num의 값이 100 미만인 경우: result를 num의 단어로 설정하고, 입력값이 num의 값보다 크면 남은 값(입력값 − num의 값)에 대해 solve()를 재귀 호출한 결과를 공백과 함께 덧붙입니다.
- 반복문을 종료합니다.
- 최종적으로 result를 반환하며, solve(입력값)을 호출하면 원하는 결과를 얻을 수 있습니다.
구현 예제
더 나은 이해를 돕기 위해 아래의 C++ 구현 코드를 살펴보겠습니다.
#include<bits/stdc++.h>
using namespace std;
vector<pair<string, int>> numbers{{"Billion", 1000000000},
{"Million", 1000000},
{"Thousand", 1000},
{"Hundred", 100},
{"Ninety", 90},
{"Eighty", 80},
{"Seventy", 70},
{"Sixty", 60},
{"Fifty", 50},
{"Forty", 40},
{"Thirty", 30},
{"Twenty", 20},
{"Nineteen", 19},
{"Eighteen", 18},
{"Seventeen", 17},
{"Sixteen", 16},
{"Fifteen", 15},
{"Fourteen", 14},
{"Thirteen", 13},
{"Twelve", 12},
{"Eleven", 11},
{"Ten", 10},
{"Nine", 9},
{"Eight", 8},
{"Seven", 7},
{"Six", 6},
{"Five", 5},
{"Four", 4},
{"Three", 3},
{"Two", 2},
{"One", 1}};
string solve(int input) {
if (input == 0) return "Zero";
string result;
for (auto& num : numbers) {
if (num.second <= input) {
if (num.second >= 100) {
result = solve(input / num.second) + " " + num.first;
if (input > (input / num.second) * num.second)
result += " " + solve(input - (input / num.second) * num.second);
} else {
result = num.first + (input > num.second ? " " + solve(input - num.second) : "");
}
break;
}
}
return result;
}
int main() {
cout<< solve(5678) <<endl;
return 0;
}
실행 결과
입력
5678
출력
Five Thousand Six Hundred Seventy Eight
동작 원리 살펴보기
입력값이 5678일 때 알고리즘이 실제로 어떻게 동작하는지 단계별로 확인해 보겠습니다.
- 5678은 1000 이상이므로 solve(5678 ÷ 1000) = solve(5) = "Five"가 먼저 계산되고, 여기에 "Thousand"가 붙어 "Five Thousand"가 완성됩니다.
- 나머지 678은 100 이상이므로 solve(678 ÷ 100) = solve(6) = "Six"에 "Hundred"가 붙어 "Six Hundred"가 됩니다.
- 남은 78은 90보다 작고 70 이상이므로 "Seventy"가 선택되고, solve(8) = "Eight"가 뒤에 연결됩니다.
- 모든 조각이 합쳐져 최종적으로 "Five Thousand Six Hundred Seventy Eight"가 출력됩니다.
이처럼 큰 단위부터 차례대로 값을 분해하고 재귀 호출로 나머지를 처리하면, 복잡한 숫자도 체계적으로 영어 단어로 변환할 수 있습니다.