AJ

안녕하세요

2 분 소요

[DP] 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, …


제한사항

  • 인자: n은 number 타입의 자연수 (n >= 1)
  • number 타입을 리턴해야 합니다.
  • ugly numbers를 배열에 저장했을 때, n번째 ugly number의 위치는 인덱스 n-1 입니다.


입출력 예

let result = uglyNumbers(1);
console.log(result); // --> 1

result = uglyNumbers(3);
console.log(result); // --> 3


풀이

DP 단순히 처음부터 끝까지 모든 수에 대해서 나눗셈 연산을 하는 naive solution 작성시 시간초과로 통과되지 않는다. ugly number에 2, 3 또는 5를 곱한 수 역시 ugly number 이기 때문에 나눗셈 연산을 매번 다시 할 필요가 없다. (O(N))

const uglyNumbers = function (n) {
  if (n === 1) return 1;

  let list = [1];
  let multiples = [2, 3, 5];
  let cand = [];

  while (list.length < n) {
    list.forEach((el) => {
      multiples.forEach((mul) => {
        if (!cand.includes(el * mul) && list[list.length-1] < el * mul) {
          cand.push(el * mul);
        }
      })
    });
    cand.sort((a,b) => a - b);
    list.push(cand.shift());
  }
  return list[n-1];
};


Reference

// naive solution
// const uglyNumbers = function (n) {
//   const isUgly = (num) => {
//     num = decompose(num, 2);
//     num = decompose(num, 3);
//     num = decompose(num, 5);
//     return num === 1;
//   };

//   const decompose = (num, factor) => {
//     while (num % factor === 0) num = num / factor;
//     return num;
//   };

//   let num = 0;
//   let cnt = 0;
//   while (n > cnt) {
//     num++;
//     if (isUgly(num)) cnt++;
//   }
//   return num;
// };

// O(N)
const uglyNumbers = function (n) {
  // 매번 나눗셈 연산을 하는 것이 비효율적이므로
  // 이미 구한 수에서부터 구한다.

  const uglyNumbers = [1];
  let idx2 = 0,
    idx3 = 0,
    idx5 = 0;

  for (let i = 0; i < n; i++) {
    // 1. 가장 작은 수인 1에 2, 3, 5를 곱한 수 중에 가장 작은 수를 구한다.
    // 2. 2가 선택됨.
    // 3. 2는 가장 작은 수 1에 곱해졌으므로
    //   3.1 이제 2는 그 다음 작은 수인 2에 곱해지고
    //   3.2 3, 5는 여전히 가장 작은 수에 곱해진다.
    // 4. 3에서 가장 작은 수는 3. 3은 이제 다음으로 작은 수인 2에 곱혀진다.
    // 5. 반복
    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];
};




맨 위로

참고