이 문제의 과제는 주어진 수 N의 각 자릿수 계승(팩토리얼)의 곱과 동일한 값을 가지면서, 앞이나 뒤에 붙는 0 또는 1을 포함하지 않는 최대 수를 찾는 것입니다.
예시를 통해 문제를 이해해 보겠습니다.
예시
- 입력 − N = 4912
- 출력 − 73332222
- 설명 − 4! × 9! × 1! × 2! = 7! × 3! × 3! × 3! × 2! × 2! × 2! × 2! = 17,418,240
- 입력 − N = 340
- 출력 − 3322
문제 해결 접근 방법
- 최대한 큰 답을 얻으려면 주어진 수를 소수들의 계승 곱으로 표현해야 합니다. 소수가 아닌 자릿수(4, 6, 8, 9)는 더 작은 소수의 계승으로 분해될 수 있어, 그 결과로 만들어지는 수가 더 커지기 때문입니다.
만약 주어진 수가 0과 1로만 이루어져 있다면 새로운 결과를 만드는 것은 불가능하므로 원래 값을 그대로 반환합니다. - MaxNum() 함수에서는 int형 변수
total_digits를 선언해 전체 자릿수를 저장하고, 각 숫자의 등장 횟수를 저장할 int형 배열Frq[] = {0}을 초기화합니다. - i=0부터 i<total_digits까지 반복하면서 각 자릿수가 소수인지 검사합니다.
- 현재 자릿수가 소수(1, 2, 3, 5, 7)라면 해당 위치의 Frq[] 값에 1을 더합니다.
- 소수가 아니라면 별도의 if문으로 4, 6, 8, 9 중 해당하는지 확인한 뒤, 기본 소수 계승으로 분해하여 빈도를 증가시킵니다.
− 4! = 3! × 2! × 2!
− 6! = 5! × 3!
− 8! = 7! × 2! × 2! × 2!
− 9! = 7! × 3! × 3! × 2! - 최종 답을 저장할 빈 문자열
ans를 생성합니다. - 마지막 단계로 넘어가기 전에, 수가 0과 1로만 이루어져 있는지 확인합니다. 그렇다면 원래 문자열을 그대로 반환하고, 아니라면 다음 단계로 진행합니다.
- i=9부터 i>=2까지 내림차순으로 반복하며 변수
C = Frq[i]를 초기화합니다. 내부의 while(C--) 루프에서ans += (char)(i + 48)을 실행해 최종 답을 문자열에 차례로 추가합니다. 큰 숫자부터 채우기 때문에 자연스럽게 최댓값이 만들어집니다.
구현 예제
#include <bits/stdc++.h>
using namespace std;
string MaxNum(string str){
int total_digits = str.length();
int Frq[15] = { 0 };
//각 자릿수의 빈도 구하기
for (int i = 0; i < total_digits; i++){
if (str[i] == '1'|| str[i] == '2'|| str[i] == '3'|| str[i] == '5'|| str[i] == '7'){
Frq[str[i] - 48] += 1;
}
// 4! = 3! * 2! * 2!
if (str[i] == '4'){
Frq[2] += 2;
Frq[3]++;
}
// 6! = 5! * 3!
if (str[i] == '6'){
Frq[5]++;
Frq[3]++;
}
// 8! = 7! * 2! * 2! * 2!
if (str[i] == '8'){
Frq[7]++;
Frq[2] += 3;
}
// 9! = 7! * 3! * 3! * 2!
if (str[i] == '9'){
Frq[7]++;
Frq[3] += 2;
Frq[2]++;
}
}
string ans = "";
//숫자가 1 또는 0으로만 구성된 경우
if (Frq[1] == total_digits || Frq[0] == total_digits || (Frq[0] + Frq[1]) == total_digits){
return str;
}
else{
//가능한 최대 수 만들기
for (int i = 9; i >= 2; i--){
int C = Frq[i];
while (C--){
ans += (char)(i + 48);
}
}
return ans;
}
}
//메인 함수
int main(){
string str = "340";
cout << MaxNum(str);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력을 얻을 수 있습니다.
3322