알고리즘: 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 입니다.

입출력 예시

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

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

Advanced

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

힌트

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

풀이

1. (2, 3, 5)만을 사용하여 곱한 결과를 오름차순대로 나열하는 것이 포인트
2. let result = [1]를 선언하고 result[0]을 1로 고정시킨다
3. result[0]에 각각 2, 3, 5로 곱한 값을 따로 변수선언한다
4. Math.min()을 통해 그 중 최소값을 뽑아 result.push(최소값)으로 result 배열에 밀어 넣는다
5. 최소값으로 뽑힌 값은 index++를 적용한다
6. 계속 비교한다
7. result[n-1]의 값을 구한다

const uglyNumbers = function (n) {

  const result =[1];
  
  let idx2 = 0;
  let idx3 = 0;
  let idx5 = 0;
  
  for(let i = 0; i < n; i++) {
  	let mulBy2 = result[idx2] * 2;
    let mulBy3 = result[idx3] * 3;
    let mulBy5 = result[idx5] * 5;
    
    let nextNum = Math.min(mulBy2, mulBy3, mulBy5);
    result.push(nextNum);
    
    if(nextNum === mulBy2) idx2++;
    if(nextNum === mulBy3) idx3++;
    if(nextNum === mulBy5) idx5++;
  }
	return result[n-1];
}

한 줄 평

• mulBy2 = 2 * 3 && mulBy3 = 3 * 2가 되는 등 중복값이 나오는 경우가 있다
• 이 경우 Math.min(mulBy2, mulBy3, mulBy5) = 6으로 나온다
• 중복이긴 하지만 mulBy2와 mulBy3 모두 최소값으로 간주한다
• 따라서 마지막 if절에서 idx2와idx3 모두 +1씩 된다
• 결론적으로 result 배열에 6이 2번 들어갈 일은 없드아