소인수분해란?

1보다 큰 자연수를 소인수(소수인 인수)들만의 곱으로 나타내는 것 또는 합성수를 소수의 곱으로 나타내는 방법

예시)

보통 8을 인수로 나누면 (1,2,4,8)이런 씩으로 나눌 수가 있다. 여기서 소인수(소수로 이루어진 인수)로 나누면 2 * 2 * 2 라는 소인수분해를 할 수가 있다.

문제

• 2, 3, 5로만 나누어 떨어지는 수로 이루어진 uglynumber들 중에 n번째의 수는 무엇인지 리턴하시오.

• uglynumber: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16...

풀이

• n보다 작은 수 전부를 2,3,5로만 나누어지는 확인을 한 후 uglynumber라는 배열에 넣어 줄 수 있지만, 그러기에는 시간이 많이 걸리기 때문에, 역으로 2,3,5를 곱해주는 형식으로 진행한다.

주의 사항

• 소인수분해임으로 증가되는 수들을 곱해주는 것이 아닌 곱했던 수에 다시 곱해서 소인수로 이루어진 수를 배열에 넣어준다.
  예시)
  현재 위치: 12 (232)
  다음 위치: 16 (2222)
  (2의 배수들 중 12 다음의 14는 (27)로 소인수는 맞지만 문제가 원하는 (2,3,5)로만 이루어지지 않기 때문에 주의해준다.

• Ugly number는 오름차순으로 정렬된 배열이여야 한다.

코드

const uglyNumbers = function (n) {

  let [i2,i3,i5] = [0,0,0] // 2,3,5각각 증가될 값들
  let result = [1] // 결과값인 uglynumber의 배열
  let multi = [0,0,0] // 곱해진 값들을 비교할 배열
  let next = 0 // uglynumber배열에 다음으로 들어올 값

  for(let i = 1; i <= n ; i++){
    // uglynumber에 있는 소수와 곱했을 때 나올 값들
    multi[0] = 2 * result[i2]  
    multi[1] = 3 * result[i3]
    multi[2] = 5 * result[i5]
 	// 2,3,5로 각각 곱했을 때 가장 작은 값을 선정해 배열에 넣어준다.
	// 오름차순
 	next = Math.min(...multi)
  	result.push(next)
    
	//배열에 넣은 값의 카운트를 올려준다.
	if(next === multi[0]) i2++
  	if(next === multi[1]) i3++
  	if(next === multi[2]) i5++
    // else if문을 사용하지 않는 이유
	// 2*3, 3*2처럼 중복된 값도 있으니 2,3 같이 카운트를 올려줘야 되기 때문이다.
}

  // 사용자가 원하는 1번째는 배열의 0번째 index이다.
return result[n-1]
};