슈퍼 얼리 넘버(Super Ugly Number)란?
슈퍼 얼리 넘버는 주어진 소수 목록 primes(크기 k)에 포함된 소수들만을 인수로 가지는 양의 정수를 의미합니다. 예를 들어 n이 12이고 소수 목록이 [2, 7, 13, 19]라면, 출력 결과는 32가 됩니다. 이는 [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]가 해당 조건을 만족하는 12번째까지의 슈퍼 얼리 넘버 시퀀스이기 때문입니다.
이 문제를 해결하기 위해 우선순위 큐(priority queue)를 활용한 효율적인 접근 방식을 사용할 수 있습니다.
해결 알고리즘 단계
다음 단계를 따라 문제를 해결할 수 있습니다.
- num(현재 값), prime(소수), idx(인덱스) 세 개의 필드를 가진 Data 구조체를 정의합니다.
- n이 1이면 1을 반환하고, 크기가 n + 1인 배열을 생성하여 모든 값을 1로 초기화합니다.
- 우선순위 큐 pq를 선언합니다.
- i가 0부터 primes의 크기까지 반복하면서 각 소수에 대해 Data(primes[i], primes[i], 2) 객체를 생성하여 큐에 삽입합니다.
- i가 2부터 n까지 반복하면서 다음 작업을 수행합니다.
- pq의 최상단 요소를 curr로 가져온 뒤 큐에서 제거합니다.
- val := curr.num으로 설정하고, v[i] := val로 저장합니다.
- curr.num := curr.prime * v[curr.idx]로 갱신한 후 idx를 1 증가시키고 curr을 다시 큐에 삽입합니다.
- val과 pq 최상단의 num 값이 같은 동안 중복 값을 제거하기 위해 위 과정을 반복합니다. 이는 동일한 수가 여러 소수 조합으로 생성되는 경우를 방지합니다.
- 최종적으로 v[n]을 반환합니다.
C++ 구현 예제
아래 코드를 통해 실제 구현 방법을 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
struct Data{
int num, prime, idx;
Data(int a, int b, int c){
num = a;
prime = b;
idx = c;
}
};
struct Comparator{
bool operator()(Data a, Data b){
return !(a.num < b.num);
}
};
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
if(n == 1)return 1;
vector <int> v(n + 1, 1);
priority_queue < Data, vector < Data >, Comparator > pq;
for(int i = 0; i < primes.size(); i++){
pq.push(Data(primes[i], primes[i], 2));
}
int x;
for(int i = 2; i <= n; i++){
Data curr = pq.top();
pq.pop();
int val = curr.num;
v[i] = val;
curr.num = curr.prime * v[curr.idx];
curr.idx++;
pq.push(curr);
while(val == pq.top().num){
curr = pq.top();
pq.pop();
curr.num = curr.prime * v[curr.idx];
curr.idx++;
pq.push(curr);
}
}
return v[n];
}
};
main(){
Solution ob;
vector<int> v = {2,7,13,19};
cout << (ob.nthSuperUglyNumber(12, v));
}입력
12 [2,7,13,19]
출력
32
알고리즘 핵심 포인트
이 알고리즘의 시간 복잡도는 O(n × log k)입니다. 여기서 n은 찾고자 하는 슈퍼 얼리 넘버의 순서, k는 소수 목록의 크기를 의미합니다. 우선순위 큐를 사용함으로써 매번 다음으로 작은 후보 값을 로그 시간 안에 효율적으로 찾을 수 있으며, 중복 처리 로직을 통해 같은 값이 시퀀스에 여러 번 포함되는 것을 방지합니다. 이는 다이나믹 프로그래밍 기반의 멀티 포인터(multi-pointer) 방식과 결합된 형태로, 각 소수마다 자신이 곱해질 배열의 위치(idx)를 추적하는 방식입니다.