LeetCode (C/C++) 313. Super Ugly Number

https://leetcode.com/problems/super-ugly-number/description/

---

풀이 1

우선순위 큐를 사용, 적은 수부터 계산했다. 

현재 수에 prime 수들을 곱해 ugly number를 찾는다. 이 때 곱한 값이 signed int 범위 내에 있는지 확인하고, 이를 우선순위 큐에 넣는다. 

큐에서 꺼낼 때에는 같은 값을 모두 큐에서 빼며 중복값을 제거했다.

 

위의 방법이 너무 느려 다른 사람들의 풀이를 봤고, 다른 방법으로 풀어보았다.

 

풀이 2

n만큼 순회하며 n번째 ugly number를 찾는다.

우선순위 큐에 {현재 숫자, prime 숫자, 인덱스}를 저장하고, 하나씩 꺼내면서 현재숫자와 직전 ugly number를 비교하며 중복값을 제거한다. (중복값은 삽입하지 않는다)

우선순위 큐에 다음 값을 삽입할 때는 인덱스 값을 확인, 현재 prime의 다음 ugly number를 찾아 삽입한다.

 

 

이 코드의 시간복잡도가 더 빠르지만 vector등의 문법 때문에 시간이 더 오래 걸리는 듯 했다. 

---

코드 1

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        // n = 1일 때 예외 처리
        if (n == 1)
            return 1;

        priority_queue<int, vector<int>, greater<int>> q;
        q.push(1);

        int now;
        while (n--) {
            now = q.top();
            q.pop();
            
            // 중복 제거
            while (q.size() && now == q.top())
                q.pop();
            
            // 현재 수에 prime을 곱해 ugly number 구하기
            for (int prime : primes) {
                
                // int 범위 체크
                if ((long long) now * prime > INT_MAX) break;
                int next = now * prime;
                q.push(next);
            }
        }
        return now;
    }
};

 

코드 2

class Solution {
public:
    typedef vector<long long> vi;
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        if (n == 1)
            return 1;

        priority_queue<vi, vector<vi>, greater<vi>> q;
        for (int prime : primes)
            q.push({prime, prime, 0});
            
        int nums[n];
        for (int i = 1; i < n; ) {
            auto now = q.top();
            q.pop();

            // 현재 수, 인덱스를 사용
            long long num = now[0], prime = now[1], idx = now[2];
            if (nums[i - 1] != num)
                nums[i++] = num;
            q.push({nums[idx + 1] * prime, prime, idx + 1});
        }
        
        // n번째 ugly number 반환
        return nums[n - 1];
    }
};