C++의 매우 못생긴 숫자

n번째 엄청나게 못생긴 숫자를 찾기 위해 하나의 함수를 만들어야 합니다. 매우 못생긴 숫자는 모든 소수가 k 크기의 주어진 소수 목록 소수에 있는 양수입니다. 따라서 n이 12이고 소수가 [2, 7, 13, 19]이면 출력은 32가 됩니다. 이는 [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]는 12개의 엄청나게 못생긴 숫자의 시퀀스입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

num, prime 및 idx를 사용하여 데이터 구조 삼중항을 생성합니다.
n이 1이면 1을 반환하고 n + 1 크기의 배열을 만들고 1로 채웁니다.
우선순위 큐 pq 정의
범위 0에서 소수 크기까지의 i에 대해 -
- 삼중항 생성 t(primes[i], 소수[i], 2)
범위 2에서 n까지의 i에 대해
- curr :=pq의 최상위 요소, pq에서 삭제
- val :=통화 수
- v[i] :=발
- num of curr :=curr의 소수 * v[index of curr]
- curr의 인덱스를 1 증가
- pq에 curr 삽입
- 동안 val =pq 상단의 수,
  - curr :=pq의 맨 위 및 pq에서 삭제
  - num of curr :=curr의 소수 * v[index of curr]
  - curr의 인덱스를 1 증가
  - pq에 curr 삽입
반환 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]