슈퍼 얼리 넘버(Super Ugly Number)란?
슈퍼 얼리 넘버는 모든 소인수가 주어진 소수 배열(크기 k)에 속해 있는 양의 정수를 의미합니다. 예를 들어, 소수 배열이 primes = [2, 7, 13, 19]로 주어졌을 때 처음 12개의 슈퍼 얼리 넘버는 다음과 같습니다.
[1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]
문제 이해하기
숫자 num과 소수 배열 arr를 인자로 받아, num번째 슈퍼 얼리 넘버를 찾아 반환하는 JavaScript 함수를 작성하는 것이 목표입니다.
접근 방법
이 문제는 다이나믹 프로그래밍과 포인터 기법을 활용하면 효율적으로 해결할 수 있습니다. 각 소수마다 하나의 포인터를 두고, 해당 소수와 이미 구한 슈퍼 얼리 넘버를 곱한 값들 중 최솟값을 차례대로 선택하는 방식입니다. 이렇게 하면 중복 없이 오름차순으로 슈퍼 얼리 넘버 수열을 완성할 수 있습니다.
예제 코드
const num = 7;
const arr = [2, 7, 14, 19];
const superUgly = (num = 1, arr = []) => {
arr.sort((a, b)=> a - b);
const ptr = [];
const res = [];
for(let i=0;i<arr.length;i++){
ptr[i] = 0;
};
res.push(1);
for(let i = 1; i < num; i++){
let mn=Math.pow(2, 32) - 1;
for(let j = 0; j < arr.length; j++){
mn=Math.min(mn,arr[j]*res[ptr[j]])
};
res[i]=mn
for(let j=0; j < arr.length; j++){
if(mn % arr[j] === 0){
ptr[j]++;
};
};
};
return res[num-1]
};
console.log(superUgly(num, arr));코드 동작 원리
1. 소수 배열을 오름차순으로 정렬합니다.
2. 각 소수별로 포인터(ptr)를 초기화하고, 결과 배열(res)에 첫 번째 값 1을 저장합니다.
3. 매 단계마다 모든 소수와 자신의 포인터가 가리키는 값의 곱 중 최솟값을 찾습니다.
4. 최솟값을 결과 배열에 추가하고, 그 최솟값을 만들어낸 소수들의 포인터를 증가시킵니다.
5. 위 과정을 반복한 후 마지막 값을 반환합니다.
출력 결과
콘솔에는 다음과 같은 결과가 출력됩니다.
16