[프로그래머스] 138475 억억단을 외우자 (javascript)

문제

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

풀이

문제를 읽고 각 숫자의 약수의 개수를 구하는 문제라는 것을 바로 떠올릴 수 있었다.

다만, query가 여러 개 존재하고, 특히 범위에 대한 질의가 반복되기 때문에 매번 약수의 개수를 새로 계산하는 방식은 비효율적이라고 판단했다.

따라서 에라토스테네스의 체와 유사한 방식으로 각 수의 약수 개수를 미리 계산해 테이블화하는 접근을 선택했다.

또한 문제에서 요구하는 것이 특정 범위 내 최댓값을 찾는 것이므로 단조성, 누적 처리 등의 아이디어를 떠올렸고, 뒤에서부터 최적 값을 갱신하는 suffix DP 방식으로 해결했다.

전체 시간 복잡도는 $e$를 최대 범위, $q$를 질의의 개수라고 할 때, 약수 개수 계산이 $O(e \log e)$, 최적 값 테이블 구축이 $O(e)$, 질의 처리 자체는 $O(q)$로, 총 $O(e \log e + q)$로 예상된다.

정답 코드

const solution = (e, starts) => {
    const counts = new Array(e + 1).fill(0);
    const best = new Array(e + 1);
    
    for (let i = 1; i <= e; i++) {
        for (let j = i; j <= e; j += i) {
            counts[j] += 1;
        }
    }
    
    best[e] = e;
    for (let i = e - 1; 0 < i; i--) {
        best[i] = counts[i] < counts[best[i + 1]] ? best[i + 1] : i;
    }
    
    return starts.map((start) => best[start]);
}