[JS] 억억단을 외우자

먼저 n이란 수가 억억단에서 나오는 횟수는 n의 약수의 개수이다.

 

따라서 처음에는 n의 약수 개수를 구하는 알고리즘을 활용해서 해결해보려고 했다.

 

const getDivisorCnt = (n) => {
  let ret = 0;
  for (let i = 0; i <= n ** 0.5; i++) {
    if (!(n % i)) ret += 1;
  }
  ret *= 2;
  if (Number.isInteger(n ** 0.5)) ret -= 1;
  return ret;
};

function solution(e, starts) {
  const ret = starts.map((n) => {
    let cnt = getDivisorCnt(n);
    let ret = n;
    for (let i = n; i <= e; i++) {
      const tmp = getDivisorCnt(i);
      if (tmp > cnt) {
        cnt = tmp;
        ret = i;
      }
    }
    return ret;
  });

  return ret;
}

 

하지만 문제 케이스가 5,000,000 까지로 매우 크기때문에 위와같이 일일히 구하는건 어려웠다.

 

따라서 시간을 줄일 수 있는 2가지 방법을 생각해봤다.

 

 

1. 에라토스테네스의 체를 활용해서 1~5,000,000 까지의 약수의 개수를 모두 구한다.

2. dp를 활용해서 e~1까지의 최대 약수 개수를 가진 수를 저장한다.

=> 이 경우 역순으로 dp를 채워나가야 한다. 문제에서 e는 약수의 범위를 찾는 구간중 큰 구간으로 고정되어 있기 때문에 해당 부분부터 역순으로 찾아나가면 된다. 또한, 약수의 개수가 작은 경우에는 더 작은수가 정답이 된다는 것을 생각하자.

 

function solution(e, starts) {
  const sieve = new Array(5000001).fill(0);
  for (let i = 1; i <= e; i++) {
    for (let j = 1; j <= e / i; j++) {
      sieve[i * j]++;
    }
  }

  const ret = [e];
  for (let i = e - 1; i > 0; i--) {
    ret.push(sieve[ret[ret.length - 1]] > sieve[i] ? ret[ret.length - 1] : i);
  }
  return starts.map((n) => ret[e - n]);
}