JavaScript Algorithm - uglyNumbers

 

문제설명: 입력받은 n을 읽고 uglyNumbers의 배열의 인덱스를 반환하세요

uglyNumbers란 2,3,5로 나누어서 0이되는 값들입니다.
그러나 uglyNumbers 배열의 첫 번째값은 1입니다. 우선 전체 배열을 열거하면 다음과 같습니다. 

uglyNumbers = [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 입니다.
• 이유는 배열은 0 부터 시작하기 때문입니다.

입출력 예시

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

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

 

 

풀이 코드 설명

이 문제에 가장 효율적인 알고리즘인 다이나믹 프로그래밍을 적용한 코드입니다. 2, 3, 5를 인수로 가진 uglyNumbers들을 순회하면서 구하며 그 중 최소값을 uglyNumbers 배열에 삽입하면서 동작합니다. 시간복잡도는 O(N)으로 코드는 선형적으로 비례하는 속도로 동작합니다. 

 

function uglyNumbers(n) {
  // 1은 첫 번째 ugly number이므로, 배열에 미리 추가합니다.
  const uglyArr = [1];
  // 2, 3, 5의 인덱스를 가리키는 포인터를 초기화합니다.
  let idx2 = 0, idx3 = 0, idx5 = 0;

  // n번째 ugly number를 찾을 때까지 2, 3, 5를 인수로 갖는 ugly number를 생성합니다.
  while (uglyArr.length < n) {
    // 2, 3, 5를 곱한 수 중 가장 작은 수를 선택합니다.
    const nextUgly = Math.min(uglyArr[idx2] * 2, uglyArr[idx3] * 3, uglyArr[idx5] * 5);
    console.log("nextUgly",nextUgly)
    // 선택된 ugly number를 배열에 추가합니다.
    uglyArr.push(nextUgly);
    console.log("uglyArr",uglyArr)
    // 선택된 ugly number에 대해 2, 3, 5 중 어느 수를 곱했는지에 따라 포인터를 이동시킵니다.
    if (nextUgly === uglyArr[idx2] * 2) {
      idx2 += 1;
    }
    if (nextUgly === uglyArr[idx3] * 3) {
      idx3 += 1;
    }
    if (nextUgly === uglyArr[idx5] * 5) {
      idx5 += 1;
    }
  }

  // n번째 ugly number를 반환합니다.
  return uglyArr[n - 1];
}

 

console.log 예시

node 35_uglyNumbers_gpt.js 
1
nextUgly 2
uglyArr [ 1, 2 ]
nextUgly 3
uglyArr [ 1, 2, 3 ]
3