반응형
문제
아래와 같이 정의된 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 입니다.
코드
// 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;
};
const uglyNumbers = function (n) {
// TODO: 여기에 코드를 작성합니다.
// 매번 나눗셈 연산을 하는 것이 비효율적이므로
// 이미 구한 수에서부터 구한다.
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];
};
반응형
'코드스테이츠 SEB FE 41기 > 데일리 코딩(Hard)' 카테고리의 다른 글
[알고리즘/javascript][Graph] 인접 행렬 길찾기 (0) | 2022.11.18 |
---|---|
[알고리즘/javascript] [Graph] 인접 행렬 생성하기 (0) | 2022.11.18 |
[알고리즘/javascript] getItemFromTwoSortedArrays (0) | 2022.11.17 |
[알고리즘/javascript] 큐 - 심화 (0) | 2022.11.17 |
[알고리즘/javascript] 이진탐색 & 변형된 이진탐색 (0) | 2022.11.08 |