어떤 수 n이 주어졌을 때, n번째 못생긴 수(ugly number)를 찾아야 합니다. 여기서 못생긴 수란 소인수가 오직 2, 3, 5뿐인 수를 의미합니다. 예를 들어 10번째 못생긴 수는 12입니다. 처음 몇 개의 못생긴 수가 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 순으로 나열되기 때문입니다.
해결 알고리즘
이 문제는 동적 계획법(DP)의 개념을 활용하면 효율적으로 풀 수 있습니다. 이미 구한 못생긴 수에 2, 3, 5를 곱한 값 역시 반드시 못생긴 수라는 성질을 이용합니다. 세 개의 포인터(인덱스)를 두고, 각 단계마다 후보 값 중 가장 작은 것을 차례대로 배열에 채워 나갑니다.
구체적인 진행 과정은 다음과 같습니다:
- 크기가 (n + 1)인 배열 v를 정의합니다.
- n이 1이라면 1을 반환합니다.
- 세 개의 후보 변수를 초기화합니다: two := 2, three := 3, five := 5
- 세 개의 인덱스도 초기화합니다: twoIdx := 2, threeIdx := 2, fiveIdx := 2
- i := 2부터 i <= n까지 반복하며 다음을 수행합니다:
- curr := two, three, five 중 최솟값
- v[i] := curr
- curr == two라면: two := v[twoIdx] * 2 로 갱신하고 twoIdx를 1 증가
- curr == three라면: three := v[threeIdx] * 3 으로 갱신하고 threeIdx를 1 증가
- curr == five라면: five := v[fiveIdx] * 5 로 갱신하고 fiveIdx를 1 증가
- 최종적으로 v[n]을 반환합니다.
예제 코드
아래 구현을 통해 더 잘 이해할 수 있습니다:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> v(n + 1);
if(n == 1){
return 1;
}
int two = 2, three = 3, five = 5;
int twoIdx = 2;
int threeIdx = 2;
int fiveIdx = 2;
for(int i = 2; i <= n; i++){
int curr = min({two, three, five});
v[i] = curr;
if(curr == two){
two = v[twoIdx] * 2;
twoIdx++;
}
if(curr == three){
three = v[threeIdx] * 3;
threeIdx++;
}
if(curr == five){
five = v[fiveIdx] * 5;
fiveIdx++;
}
}
return v[n];
}
};
main(){
Solution ob;
cout << (ob.nthUglyNumber(15));
}입력
15
출력
24
위 코드에서 n에 15를 넣으면 24가 출력됩니다. 실제로 못생긴 수를 나열하면 15번째 값이 24임을 확인할 수 있습니다. 이 알고리즘은 매번 새로운 수를 소인수분해하지 않고 이미 계산된 값들을 재활용하기 때문에 시간 복잡도 O(n)으로 매우 효율적입니다.