(프로그래머스 JS)억억단 구하기

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

프로그래머스

 

DP와 약수의 개수를 구하는 공식을 이용해 문제 풀이.

우선 소수를 판별할 수 있는 에라토스테네스의 체 방식을 이용해 약수의 개수를 구할 수 있다는 것을 떠올렸다.

 

에라토스테네스의 체를 이용해서 각 수의 배수에 도달하면서 카운팅을 해준다.

 

카운팅이 끝나면 각 범위 내에서 카운팅이 많은 수를 구한다.

단, 카운팅이 같은 수가 여러개면 가장 작은 수를 구해야 하는 조건이 있다.

그래서 앞이 아닌 뒤로 수를 접근하는 방식을 선택했다.

 

index = 1 ~ e

count = index에 해당하는 카운팅 최대값

 

for문으로 e ~ min(starts에서의 최소값) 순서로 진행한다.

처음 시작하는 수(e)의 범위 내에서는 e가 최대값이기 때문에 max[i] = i, count = arr[i]로 시작을 한다.

이후에는 arr[i]에 있는 카운팅과 count(i ~ e까지의 카운팅 최대값)을 비교한다.

만약 arr[i] < count라면 i보다 index의 카운팅이 높다는 뜻이므로 max[i] = index를 저장한다.

그렇지 않다면 index와 count를 i에 해당하는 수로 갱신을 해주고, max[i] = i로 저장한다.

 

마지막은 starts를 순회하면서 해당하는 카운팅 값을 answer에 넣어주면 된다.

function solution(e, starts) {
    const answer = [];
    const arr = Array.from({length: 5000001}, () => 0);
    const max = Array.from({length: 5000001}, () => 0);
    let count = 0;
    let index = e;
    
    for(let i = 1; i <= e; i++) {
        for(let j = i; j <= e; j += i) {
            arr[j]++;
        }
    }
    
    for(let i = e; i >= min; i--){
        if(i == e){
            max[i] = i;
            count = arr[i];
        } else{
            if(arr[i] < count){
                max[i] = index;
            } else {
                max[i] = i;
                count = arr[i];
                index = i;
            }
        }
    }
    
    for(let i = 0; i < starts.length; i++) {
        const start = starts[i];
        
        answer.push(max[start]);
    }
    
    return answer;
}