[programmers/js] 억억단을 외자

억억단을 외자

https://school.programmers.co.kr/learn/courses/30/lessons/138475

문제 설명

억억단은 1억 x 1억 크기의 행렬입니다.
적당한 수 e를 먼저 정하여 알려주고 e 이하의 임의의 수 s를 여러 개 얘기합니다. 영우는 각 s에 대해서 s보다 크거나 같고 e 보다 작거나 같은 수 중에서 억억단에서 가장 많이 등장한 수를 답해야 합니다.
만약 가장 많이 등장한 수가 여러 개라면 그 중 가장 작은 수를 답해야 합니다.

억억단에서 1 ~ 8이 등장하는 횟수는 다음과 같습니다.

1번 등장 : 1
2번 등장 : 2, 3, 5, 7
3번 등장 : 4
4번 등장 : 6, 8

[1, 8] 범위에서는 6과 8이 각각 4번씩 등장하여 가장 많은데 6이 더 작은 수이므로 6이 정답입니다.
[3, 8] 범위에서도 위와 같으므로 6이 정답입니다.
[7, 8] 범위에서는 7은 2번, 8은 4번 등장하므로 8이 정답입니다.

풀이

숫자를 잘 보면 각 숫자가 등장하는 횟수는 약수의 개수와 같습니다.
4의 약수의 수 = 3(1, 2, 4)
6의 약수의 수 = 4(1, 2, 3, 6)

즉, e까지 약수의 수 배열에 저장하면 시간 초과 없이 답을 구할 수 있습니다.

function solution(e, starts) {
    const MAX = e;
    
    const dp = Array(MAX + 1).fill(0);
    
  	// 약수의 수 구하기 - 에라토스테네스의 체 적용
    for (let i = 1; i <= MAX; i++) {
        for (let j = i; j <= MAX; j += i) {
           dp[j] += 1;
        }
    }
    
    let maxNum = 0;
    let maxCount = 0;
    const dp2 = Array(MAX + 1).fill(0);
    
  	// 미리 최대 등장 수를 구함
    for (let i = MAX; i > 0; i--) {
        if (dp[i] >= maxCount) {
            maxCount = dp[i];
            maxNum = i;
        }
        dp2[i] = maxNum
    };
    
    return starts.map((s) => dp2[s]);
}