[LeetCode] 313. Super Ugly Number

문제 출처: https://leetcode.com/problems/super-ugly-number/

Super Ugly Number - LeetCode

 

문제

Super Ugly Number는 배열 primes의 원소가 소인수인 양의 정수를 말한다.

 

정수 n과 정수 배열 primes가 주어지면, n번째 super ugly number를 반환하라.

 

n번째 super ugly number는 32비트의 부호 있는 정수임이 보장된다.

 

예제

Input: n = 12, primes = [2,7,13,19]
Output: 32

Explanation: [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12 super ugly numbers given primes = [2,7,13,19].

Input: n = 1, primes = [2,3,5]
Output: 1

Explanation: 1 has no prime factors, therefore all of its prime factors are in the array primes = [2,3,5].

 

풀이

점진적으로 super ugly number를 추가해가는 방식을 통해 n번째 숫자를 찾아내려고 한다.

function nthSuperUglyNumber(n, primes) {
    const seq = [1];
    const pos = new Array(primes.length).fill(0);

    while (seq.length < n) {
        let minVal = primes[0] * seq[pos[0]];
        let minList = [0];

        // super ugly number의 후보군 중,
        // seq에 추가할 가장 작은 숫자 색출
        for (let i = 1; i < n; i++) {
            const val = primes[i] * seq[pos[i]];
            if (minVal > val) {
                index = i;
                minVal = val;
                minList = [i];
            } else if (minVal == val) {
                minList.push(i);
            }
        }

        seq.push(minVal);
        minList.forEach(val => pos[val] += 1);
    }

    return seq[n-1];
}

코드를 살펴보면, seq 배열은 super ugly number를 순차적으로 저장할 배열이다. pos 배열은 seq의 인덱스를 가리키고 있는 배열로 그 쓰임새는 이후 반복문에서 알 수 있다.

 

반복문(while)의 역할은 한 스텝에서 seq와 pos를 이용하여 seq에 추가될 super ugly number의 후보군을 생성하고, 그중 가장 작은 값을 찾아 seq에 추가 및 다음 스텝을 위해 pos를 업데이트하는 역할을 수행한다.

 

이 과정에서 중요한 것이 super ugly number의 후보군을 생성하는 것이다.

 

super ugly number를 생성하는 가장 손쉬운 방법은 이미 알고 있는 super ugly number에 prime[i]를 곱하는 것이다.  여기서 문제는 현재 알고 있는 super ugly number 다음으로 올 가장 작은 super ugly number가 무엇이냐는 것이다.

 

이를 아무런 정보 없이 계산한다면 알고 있는 모든 super ugly number에 primes[i]를 곱하는 반복 작업을 수행해야 한다. 하지만, 몇 번째 값을 곱해야 현재 알고 있는 가장 큰 super ugly number 보다 큰 숫자를 만드는지를 기억하고 있다면 얘기가 달라진다. 이 때문에 primes[i]가 곱해져야 할 super ugly number의 위치를 pos에 저장하여 관리하는 것으로 문제를 해결할 수 있다.

 

만약 사용하는 언어에서 우선순위 큐 자료구조를 지원한다면, 이를 활용하여 더욱 효율적인 코드를 작성할 수 있다.

 

Github: 313.js

opwe37/Algorithm-Study