문제 소개
양의 정수 x가 주어졌을 때, 각 자릿수의 곱이 x와 같아지는 가장 작은 양의 정수 b를 찾아야 합니다. 만약 조건을 만족하는 답이 존재하지 않는다면 0을 반환합니다.
예를 들어 입력이 48이라면 출력은 68입니다. 6 × 8 = 48이므로 두 자릿수의 곱이 정확히 48이 되기 때문입니다.
해결 접근 방식
이 문제는 탐욕적(Greedy) 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 답이 되는 수의 각 자릿수는 2~9 사이여야 하며, 이들의 곱이 x와 같아야 합니다.
- 자릿수가 적을수록 수가 작아지므로, 가능한 한 큰 인수(9, 8, 7...)를 먼저 묶어내야 합니다.
- 같은 자릿수 집합이라면 작은 숫자가 앞쪽(높은 자릿수)에 올 때 전체 값이 최소가 됩니다.
따라서 9부터 2까지 차례로 나누어 떨어지는 인수를 추출하고, 추출된 숫자를 결과의 뒤쪽 자릿수부터 채워 넣으면 자연스럽게 최솟값이 만들어집니다.
알고리즘 단계
- ret := 0, mul := 1로 초기화합니다.
- a가 2보다 작으면(0 또는 1) a를 그대로 반환합니다.
- i를 9부터 2까지 감소시키며 반복하면서, a가 i로 나누어 떨어지는 동안 다음을 수행합니다.
- ret := i × mul + ret (추출한 인수를 결과 뒤에 추가)
- mul := mul × 10 (자릿수를 한 칸 이동)
- a := a ÷ i (인수 제거) - 반복이 끝난 후 a가 2보다 작고 ret가 int 범위 내라면 ret를, 그렇지 않으면 0을 반환합니다.
마지막에 a가 1이 아니라면 x를 2~9의 곱으로 완전히 분해할 수 없다는 뜻이므로 답이 없는 경우입니다. 또한 ret가 int 최댓값(INT_MAX)을 초과하면 오버플로우로 판단하여 0을 반환합니다. 이를 위해 계산 과정에서는 long long 타입을 사용합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int smallestFactorization(int a) {
lli ret = 0;
lli mul = 1;
if (a < 2)
return a;
for (lli i = 9; i >= 2; i--) {
while (a % i == 0) {
ret = i * mul + ret;
mul *= 10;
a /= i;
}
}
return a < 2 && ret < INT_MAX ? ret : 0;
}
};
main(){
Solution ob;
cout << (ob.smallestFactorization(48));
}
입력
48
출력
68
동작 과정 살펴보기
입력 48에 대해 코드가 어떻게 동작하는지 단계별로 확인해 보겠습니다.
- i = 9: 48은 9로 나누어 떨어지지 않으므로 건너뜁니다.
- i = 8: 48 % 8 == 0 → ret = 8, mul = 10, a = 6
- i = 7: 나누어 떨어지지 않음
- i = 6: a = 6이므로 나누어 떨어짐 → ret = 6 × 10 + 8 = 68, mul = 100, a = 1
- 반복 종료 후 a = 1(< 2)이고 ret = 68이 int 범위 내이므로 68을 반환합니다.
이처럼 큰 인수를 낮은 자릿수에 배치하는 탐욕적 선택 덕분에, 각 자릿수의 곱이 입력값과 같으면서도 가장 작은 수를 얻을 수 있습니다.
시간 복잡도
x를 2~9 사이의 인수로 반복해서 나누는 과정에서 각 나눗셈은 x를 지수적으로 줄이므로, 전체 시간 복잡도는 O(log x)로 매우 효율적입니다.