[Javascript] 프로그래머스 - 억억단을 외우자

문제 설명

영우는 1억 x 1억 크기의 억억단을 외우기로 했고, 친구 수연은 이를 활용한 퀴즈를 냈다. 수연은 먼저 특정 수 e를 정하고, e 이하의 여러 개의 s를 제시한다. 각 s에 대해 s 이상 e 이하의 수 중에서 억억단에서 가장 많이 등장한 수를 찾아야 한다. 등장 횟수가 같다면 가장 작은 수를 선택한다.

---

제한 사항

• 1 ≤ e ≤ 5,000,000
• 1 ≤ starts의 길이 ≤ min {e, 100,000}
• 1 ≤ starts의 원소 ≤ e
• starts에는 중복된 원소가 존재하지 않음

---

해결 방법

알고리즘: 에라토스테네스의 체 방식의 약수 개수 계산 + DP 활용

1. 약수 개수 계산
   • countArr[i]를 i의 약수 개수로 설정한다.
   • 1부터 e까지 모든 숫자 i에 대해 i의 배수들에게 1씩 더해주며 약수 개수를 구한다.
   • 이 과정은 O(e log e)의 시간 복잡도를 가진다.
2. 가장 많이 등장한 수 미리 계산
   • best[i]는 i 이상 e 이하의 수 중에서 약수 개수가 가장 많은 수를 저장한다.
   • e에서부터 역순으로 탐색하며, best[i]를 best[i+1]과 비교하여 더 많은 약수를 가지는 수를 저장한다.
   • 이 과정은 O(e)의 시간 복잡도를 가진다.
3. 각 starts에 대해 정답 찾기
   • best[starts[i]]를 바로 가져와 답을 찾는다.
   • 이 과정은 O(1)의 시간 복잡도를 가진다.

---

시간 복잡도

• 약수 개수 계산: O(e log e)
• 가장 많이 등장한 수 계산: O(e)
• 결과 조회: O(1) (각 starts에 대해)
• 전체 시간 복잡도: O(e log e) + O(e) + O(|starts|) ≈ O(e log e)

---

구현 코드

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

  const best = new Array(e + 1);
  best[e] = e;
  for (let i = e - 1; i >= 1; i--) {
    best[i] = countArr[i] >= countArr[best[i + 1]] ? i : best[i + 1];
  }

  const answer = new Array(starts.length);
  for (let i = 0; i < starts.length; i++) {
    answer[i] = best[starts[i]];
  }
  return answer;
}