[Algorithm] Ugly Number 구하기 (Node.js)

 

문제

 

uglyNumber는 2,3,5로만 나누어 떨어지는 숫자입니다. 주어진 n번째 uglyNumber을 반환합니다.

uglyNumber

• uglyNumber는 2,3,5로만 나누어 떨어지는 숫자입니다.
• 1번째 uglyNumber은 1입니다.
• uglyNumber = 1,2,3,4,5,6,8,9,10,12,15,16 ...

 

 

 

입/출력

 

입력

number >= 1

 

출력

number 타입을 반환합니다.

 

주의사항

 

uglyNumber을 배열에 저장할 때 n번째 uglyNumber은 n-1 인덱스를 가집니다.

 

 

풀이

 

 

uglyNumber은 소수(Prime Number)와 맥을 같이 합니다. 우선 소수를 구하는 로직은 다음과 같습니다.

const checkPrime = (num) =>{
    for(let i=2; i<num; i++){
        if(num % i === 0 ) return false;
    }
    return true;
}

let n = 0;
const res = [];
while(n<50){
    if(checkPrime(n)) res.push(n);
    n++;
}

console.log(res);

[
   0,  1,  2,  3,  5,  7, 11,
  13, 17, 19, 23, 29, 31, 37,
  41, 43, 47
]

 

uglyNumber을 구하는 간단한 방법은 주어진 숫자를 나누어 가는 방법도 있지만 반대로 1번째 uglyNumber에서 2,3,5를 곱해 나가는 방법도 있습니다.

uglyNumber을 담을 res 배열을 선언하고, 1을 추가합니다. uglyNumber을 구성하는 2,3,5를 담은 modNum 배열을 선언합니다. 

const res = [1];
const modNum = [2,3,5];
let num=0;

 

 

주어진 입력값의 3배수만큼 반복문을 순회합니다. 기본적인 로직은 BFS 로직과 유사합니다. 배열의 요소를 꺼내와 2,3,5를 곱한 후 중복을 제거한 숫자를 결과값에 추가합니다. 

while(res.length < n*3){
  let temp = res[num];
  for(let i=0; i<modNum.length; i++){
    const x = temp * modNum[i];
    if(!res.includes(x)){
        res.push(x);
    }
  }
  num++;
}

 

결과값을 정렬하여 n-1 번째 인덱스로 n번째 uglyNumber을 출력합니다.

return res.sort((a,b)=>a-b)[n-1];

 

전체 소스코드

const uglyNumbers = function (n) {
  
    const res = [1];
    const modNum = [2,3,5];
    let num=0;
  
    while(res.length < n*3){
      let temp = res[num];
      for(let i=0; i<modNum.length; i++){
        const x = temp * modNum[i];
        if(!res.includes(x)){
            res.push(x);
        }
      }
      num++;
    }
    return res.sort((a,b)=>a-b)[n-1];
  };

 

소스코드 2

const uglyNumbers = function (n) {
  
    const uglyNumbers = [1];
    let idx2=0, idx3=0, idx5 = 0;

    for(let i=0; i<n; i++){
      const uglyNumOf2 = uglyNumbers[idx2] * 2;
      const uglyNumOf3 = uglyNumbers[idx3] * 3;
      const uglyNumOf5 = uglyNumbers[idx5] * 5;

      const nextUglyNum = Math.min(
        uglyNumOf2,
        uglyNumOf3,
        uglyNumOf5
      )
      uglyNumbers.push(nextUglyNum);

      if(nextUglyNum === uglyNumOf2) idx2++;
      if(nextUglyNum === uglyNumOf3) idx3++;
      if(nextUglyNum === uglyNumOf5) idx5++;
    }
    return uglyNumbers[n-1];
  };

 

 

[Algorithm] 힙 정렬(Heap Sort) 구현하기 Node.js/Javascript

 

[Algorithm] 동적 프로그래밍 LIS 문제 (Memoization VS Tabulation)

 

[Algorithm] 최대 이진 힙 구현하기 Node.js/Javascript