[알고리즘] uglyNumbers

간만에 래퍼런스 안 보고 혼자서 수도코드 만들어서 테스트 통과 성공했다!
통과 후 래퍼런스 확인해보니 생각의 골자는 비슷한 것 같다. (나눗셈 이용)

uglyNumber라는 수들은 2,3,5로만 나뉘어지는 숫자들인데
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16,...]과 같이 이어진다.

구해야 할 것은 n번째의 uglyNumber이다.
(주의할 점 : ugly numbers를 배열에 저장했을 때, n번째 ugly number의 위치는 인덱스 n-1 이다.)

핵심은 모든 수를 하나하나 2,3,5로 나누어보는 게 아니라 반대로 곱셈을 이용하는 것인데, 만들어진 uglyNumber에 2,3,5를 곱하면 또 uglyNumber가 된다는 게 핵심이다.

내가 짠 수도 코드

 //배열을 만들 때, uglyNumber를 담을[1]만 들어간 배열을 하나 만들고 
  //[2,3,5]가 들어있는 배열을 하나 더 만들어서
  //바깥 반복문에서는 uglyNumber에 해당하는 값을 차례로 push 해줄 것임.
  // queue 배열을 하나 만들어 준다. (용도는 계산된 수들을 담아두는 용도)
  //바깥 반복문에서는 0부터 인덱스가 i<n-1까지 돌려준다.
  //(이미 uglyNumber에 1을 담아둬서 n-1번을 돌리는 것)
  //내부 반복문은 uglyNumber의 i번째 인덱스에 2,3,5를 한 번씩 곱하도록 한다 (두번째 줄에서 만든 2,3,5가 담긴 배열을 이용)
  //위에서 계산된 수들은 중복되지 않는다면 queue속에 넣어준다.(includes)
  //바깥 반복문 마지막에서 그 셋 중에 가장 작은 수를 uglyNumber에 push 하고, queue에서 지워준다. 
  //반복한 뒤 uglyNumber[uglyNumber.length -1] 반환 

코드로 구현

const uglyNumbers = function (n) {

  const uglyArr = [1];
  const calArr = [2,3,5];
  const queue = [];
  let cal;
  let min;
  
  for(let i = 0; i<n-1;i++){
    for(let j=0;j<calArr.length;j++){
      cal = uglyArr[i]*calArr[j]
      if(!queue.includes(cal)){
      queue.push(cal)
      }
    }
    min = Math.min(...queue)
    uglyArr.push(min)
    let idx = queue.indexOf(min)
    queue.splice(idx,1)
  }

  return uglyArr[uglyArr.length-1]
};

래퍼런스

// 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];
};