프로그래머스 [Lv. 3] 억억단을 외우자 {언어 : JavaScript} [다시 풀어 보기]

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/138475?language=javascript

프로그래머스

정답 코드

function solution(e, starts) {
    // 각 수의 약수 개수를 저장할 배열
    let dp = Array.from({ length: e + 1 }, () => 0);

    // 핵심
    // 모든 수에 대해 약수 개수 계산
    for (let i = 1; i <= e; i++) {
        for (let j = i; j <= e; j += i) {
            dp[j]++;
        }
    }
    // 뒤에서부터 최대 값으로 치환
    let results = Array.from({ length: e + 1 }, () => 0);
    let maxCnt = 0;
    let maxNum = 0;
    for (let back = e; back > 0; back--) {
        const currentCnt = dp[back];
        if (currentCnt > maxCnt) {
            maxCnt = currentCnt;
            maxNum = back;
        } else if (currentCnt == maxCnt) {
            maxNum = back;
        }
        results[back] = maxNum;
    }
    
    const answer = starts.map((e) => results[e]);
    return answer;
}

풀이 방법

• 각 숫자의 약수 개수를 구한 뒤
• 뒤에서 부터 앞으로 오며 최대 개수 이면서 가장 작은 숫자를 갱신해준다.
• 갱신한 값들을 바탕으로 answer를 만들면 끝!

느낀점

• 처음 생각한 방법 = 1부터 5,000,000까지 숫자 마다 약수의 개수를 구해서 dp에 넣는 것(시간초과) = O( e * √e )
• 현재의 방법 = O(e log e)
• n = 1,000,000일 때:
  • √n = 1,000
  • log₂ n = 20
• 모르면 외워야 한다.