[LeetCode] 264. Ugly Number II

https://leetcode.com/problems/ugly-number-ii/description/?envType=daily-question&envId=2024-08-18

leetcode - Ugly Number II

문제 유형 : 우선순위 큐, 수학, 구현

문제 난이도 : Medium

 

문제

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Given an integer n, return the nth ugly number.

 

ugly number는 2,3,5만을 소인수로 갖는 양의 정수이다.

n이 주어지면, n번째 ugly number를 구하시오.

 

풀이

1은 2, 3, 5를 각각 0개씩 갖고 있는 양의 정수이므로, ugly number이다.

즉, 1이 최초의 ugly number이다.

 

방법 1 - 우선순위 큐를 이용

최소 힙에 1을 최초로 넣고, top 요소를 제거하고 각각 2,3,5를 곱해서 다시 최소 힙에 넣는다. 이들은 모두 ugly number들이다.

 

방법 2 - 배열에 채우기

i2, i3, i5를 이용하여 현재 가장 작은 ugly number에 2,3,5를 곱하여 만들 수 있는 다음 수를 추적한다.

현재 인덱스의 수에 i2 * 2, i3 * 3, i5 * 5를 비교하여 가장 작은 수를 현재 인덱스에 저장하고, 그 저장한 수에 따라서 i2, i3, i5인덱스를 증가한다.

만약 i2로 만든 수가 가장 작았다면, i2의 인덱스를 높여서 다음 수 2를 곱하는 수를 추적하는 것이다.

 

코드

C++

 

1 - 우선순위 큐를 이용

class Solution {
public:
    int nthUglyNumber(int n) {
        priority_queue<int, vector<int>, greater<int>> pq;
        set<int> s;
        pq.push(1);
        while(true) {
            long long x = pq.top();
            if(--n <= 0) return x;
            pq.pop();
            s.erase(x);

            if(x*2 <= INT_MAX && s.find(x*2) == s.end()) {
                pq.push(x*2);
                s.insert(x*2);
            }
            if(x*3 <= INT_MAX && s.find(x*3) == s.end()) {
                pq.push(x*3);
                s.insert(x*3);
            }
            if(x*5 <= INT_MAX && s.find(x*5) == s.end()) {
                pq.push(x*5);
                s.insert(x*5);
            }
        }
        return -1;
    }
};

 

2- 배열에 ugly number 채우기

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> arr(n+1);
        int i2, i3, i5;
        i2 = i3 = i5 = 1;
        arr[1] = 1;

        for(int i = 2; i < n+1; i++) {
            int i2ug = arr[i2] * 2;
            int i3ug = arr[i3] * 3;
            int i5ug = arr[i5] * 5;

            arr[i] = min(i2ug, min(i3ug, i5ug));
            
            if(arr[i] == i2ug) i2++;
            if(arr[i] == i3ug) i3++;
            if(arr[i] == i5ug) i5++;
        }

        return arr[n];
    }
};