Algorithm problem-35

1. 문제

• 2,3,5의 배수로만 이루어진 배열의 N번째 수를 리턴
• 배열의 1번째 수는 1이다

2. 시도

• 피보나치의 메모이제이션을 참고해서 풀어보려고 시도하였음

3. 수도코드

메모이제이션을 쓰려고 했는데, 이 방법은 아닌 것 같음
굳이 계산하는데 메모리까지 쓸 필요가 없는 듯, O(N)이 효율적일 듯
const uglyNumbers = function (n) {
  // 저장해둘 배열 선언
  // 1번이 1이기에, 인덱스 계산을 쉽게 하기 위해 0번 자리에 0을 넣음
  let nums = [0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16];
  // n번째 수가 없다면, 계산으로 채워줘야 함
  // 2,3,5의 배수들로만 이루어진 수의 배열임
  // 내부함수를 작성해서 배수들을 채워 넣어야 할 듯?
  function cal(n) {
    if (nums[n] === undefined) {
      // 배수를 계산해서 채워 넣어서 nums의 [n]이 채워질 때까지?
    }
  }
  // n - 1번째 수를 리턴
  return num[n]
};
1을 시작수로
2,3,5의 배수를 차례대로 리턴

4. 레퍼런스

const uglyNumbers = function (n) {
  // 저장 배열을 만들고
  let nums = [1];
  // 카운팅 방식의 계산법
  let sec = 0, trd = 0, fif = 0;
  // 반복문으로 작성, 2,3,5의 배열이니 각 배수를 계산
  // 0번 인덱스와 곱한 수들 중 가장 작은 수를 더해주고
  // 그 작은 수의 배수는 0번 인덱스는 계산해봤으니 1번 인덱스로 넘기고
  // 다른 애들은 아직 안들어갔으니 0번 인덱스와 마저 계산시키고
  for (let i = 1; i < n; i++) {
    const two = nums[sec] * 2;
    const thr = nums[trd] * 3;
    const fiv = nums[fif] * 5;
    // 현재 계산되는 배수 중 가장 작은 수를 찾고 그 수를 배열에 저장
    let minVal = Math.min(two, thr, fiv);
    nums.push(minVal);
    // 배열에 저장한 배수는 카운트를 올려서 다음 회차로 넘김
    if (minVal === two) sec++;
    if (minVal === thr) trd++;
    if (minVal === fiv) fif++;
  }
  return nums[n - 1];
}