[코딩테스트] 억억단을 외우자 [JavaScript]

문제 설명[링크]

영우는 천하제일 암산대회를 앞두고 있습니다. 암산보다는 암기에 일가견이 있는 영우는 구구단을 확장하여 억억단을 만들고 외워버리기로 하였습니다.

억억단은 1억 x 1억 크기의 행렬입니다. 억억단을 외우던 영우는 친구 수연에게 퀴즈를 내달라고 부탁하였습니다.
수연은 평범하게 문제를 내봐야 영우가 너무 쉽게 맞히기 때문에 좀 어렵게 퀴즈를 내보려고 합니다. 적당한 수 e를 먼저 정하여 알려주고 e 이하의 임의의 수 s를 여러 개 얘기합니다. 영우는 각 s에 대해서 s보다 크거나 같고 e 보다 작거나 같은 수 중에서 억억단에서 가장 많이 등장한 수를 답해야 합니다. 만약 가장 많이 등장한 수가 여러 개라면 그 중 가장 작은 수를 답해야 합니다.
수연은 영우가 정답을 말하는지 확인하기 위해 당신에게 프로그램 제작을 의뢰하였습니다. e와 s의 목록 starts가 매개변수로 주어질 때 각 퀴즈의 답 목록을 return 하도록 solution 함수를 완성해주세요.

풀이

function solution(e, starts) {
  let memo = new Array(e + 1).fill().map(_ => new Map());
  memo[1].set(1, 1);
  
  const mergeMemo = (memo1, memo2, targetMemo) => {
    for (const [key, value] of memo1) {
      if (targetMemo.has(key)) targetMemo.set(key, targetMemo.get(key) + value);
      else targetMemo.set(key, value);
    }
      
    for (const [key, value] of memo2) {
      if (targetMemo.has(key)) targetMemo.set(key, targetMemo.get(key) + value);
      else targetMemo.set(key, value);
    }
  }
  
  const getSpecial = (num) => {
    if (memo[num].size) {
      return memo[num];
    }
          
    const sqrt = Math.floor(Math.sqrt(num));
      
    for (let i = 2; i <= sqrt; i++) {
      if (num % i === 0) {
        const memo1 = getSpecial(i);
        const memo2 = getSpecial(num / i);
        mergeMemo(memo1, memo2, memo[num]);
              
        return memo[num];
      }
    }
      
    memo[num].set(num, 1);
    return memo[num];
  }
      
  for (let num = 2; num <= e; num++) {
    getSpecial(num);
  }
  
  for (let i = 0; i < memo.length; i++) {
    memo[i] = [...memo[i].values()].reduce((acc, cur) => acc * (cur + 1), 1);
  }

  let startIndex = 1;

  const getMaxIndex = (startIndex) => {
    let max = -Infinity;
    let maxIndex = -1;

    for (let i = startIndex; i < memo.length; i++) {
      const value = memo[i];
      if (value > max) {
        max = value;
        maxIndex = i;
      }
    }

    return maxIndex;
  }

  while (startIndex < memo.length) {
    const maxIndex = getMaxIndex(startIndex);
    for (let i = startIndex; i <= maxIndex; i++) {
      memo[i] = maxIndex;
    }
    startIndex = maxIndex + 1;
  }
  
  for (let i = 0; i < starts.length; i++) {
    starts[i] = memo[starts[i]]
  }

  return starts;
}

결과

테스트 9, 10에서 소요시간, 메모리 사용량이 너무 많아보인다.

시간을 내서 리펙토링이 따로 필요할 것 같다.