uglyNumbers

문제

아래와 같이 정의된 ugly numbers 중 n번째 수를 리턴해야 합니다.
ugly number는 2, 3, 5로만 나누어 떨어지는 수이다.
1은 1번째 ugly number 이다.
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, ...

입력

인자 1 : n
number 타입의 자연수 (n >= 1)

출력

number 타입을 리턴해야 합니다.

주의사항

ugly numbers를 배열에 저장했을 때, n번째 ugly number의 위치는 인덱스 n-1 입니다.

Advanced

단순히 처음부터 끝까지 모든 수에 대해서 나눗셈 연산을 하는 대신 다른 방법(O(N))을 탐구해 보세요.

힌트

나눗셈 연산을 매번 다시 할 필요가 없습니다. ugly number에 2, 3 또는 5를 곱한 수 역시 ugly number 입니다.

레퍼런스 코드(1)

• 0부터 모든 숫자를 차례로 2,3,5로 나누어떨어지는지 확인한다

const uglyNumbers = function(n){
  //숫자가 2,3,5의 배수라면, 계속 나누었을때 몫은 1이고 나머지는 0이된다
  //decompose 함수에 의해 num===1이 되면 true를
  //2,3,5의 배수가 아니어서 몫이 1이 아니라면 false를 리턴한다
  const isUgly = (num) => {
    num = decompose(num, 2);
    num = decompose(num, 3);
    num = decompose(num, 5);
    return num === 1;
  }
  //num을 factor로 나누었을때 나누어떨어지면 num에 몫을 저장한다
  //num이 factor로 더이상 나누어떨어지지 않으면, num을 리턴한다
  //decompsoe(7,2)라면 처음부터 나누어떨어지지 않으므로 7을 리턴한다
  //decompose(8,2)라면 num은 4,2,1이 되어 마지막에 1을 리턴한다
  const decompose = (num, factor) => {
    while(num%factor === 0) num=num/factor
    return num;
  }
  let num = 0; //0부터 차례로 확인하는 값
  let cnt = 0; //n===cnt가 되면 num을 리턴한다
  while(n>cnt){
    num++
    if(isUgly(num))cnt++
  }
  return num;
}

레퍼런스 코드(2)

• 배열 uglyNumbers에 2,3,5로만 나누어떨어지는 숫자를 저장한다
• n번째 수는 uglyNumbers[n-1]와 같다
• 2,3,5를 각각 곱했을때 가장 작은 수를 먼저 배열에 넣어준다
• 곱한 값과 nextUglyNum이 같을 경우 인덱스++ 해준다

//O(N)
const uglyNumbers = function(n){
  const uglyNumbers = [1];
  let idx2 = 0;
  let idx3 = 0;
  let idx5 = 0;
  for(let i=0;i<n;i++){
    const nextMultipleOf2 = uglyNumbers[idx2]*2;
    const nextMultipleOf3 = uglyNumbers[idx3]*3;
    const nextMultipleOf5 = uglyNumbers[idx5]*5;
    const nextUglyNum = Math.min(nextMultipleOf2, nextMultipleOf3, nextMultipleOf5);
    uglyNumbers.push(nextUglyNum);
    // 같은 수를 중복해서 저장할 수 있으므로, 각각 별도의 조건문으로 작성해야 한다.
    //  2 * 3 = 6
    //  3 * 2 = 6
    if(nextUglyNum === nextMultipleOf2) idx2++;
    if(nextUglyNum === nextMultipleOf3) idx3++;
    if(nextUglyNum === nextMultipleOf5) idx5++;
  }
  return uglyNumbers[n-1];
}