억억단을 외우자

수연은 영우가 정답을 말하는지 확인하기 위해 당신에게 프로그램 제작을 의뢰하였습니다. e와 s의 목록 starts가 매개변수로 주어질 때 각 퀴즈의 답 목록을 return 하도록 solution 함수를 완성해주세요.

제한사항
1 ≤ e ≤ 5,000,000
1 ≤ starts의 길이 ≤ min {e,100,000}
1 ≤ starts의 원소 ≤ e
starts에는 중복되는 원소가 존재하지 않습니다.

문제풀이

1. 전체 크기 1에서 e까지 n이 나오는 값은 n의 약수의 개수입니다.
2. starts[i]에서 e까지 가장 큰 값의 경우 e에서부터 n의 약수의 개수를 계산해 i번째까지 확인한 후 리턴해줄수 있습니다.

먼저 전체 약수의 개수를 구해야한다. 사실 이문제는 전체 약수의 개수를 한번에 찾기만한다면 어떻게든 시간초과가 뜨지않기에 해결할수있는문제이다.

대부분의 경우 각 i의 값을 전부 찾아 그 값을 넣어주는 방식으로 약수를 구하지만 이 문제에서는 그렇게하면 시간초과가 뜬다.
i부터 e까지 한번에 돌면서 약수의 값을 더해주는 방식으로 문제를 구현해야한다.

다음으로 가장 큰수 찾기는 간단하다. 뒤에서부터 가장 많은 약수의 개수를 가졌지만 가장 작은 수를 구해내면된다 (예를들어 3,8범위라면 항상 범위는 8에서 끝나니 전체범위 1~8까지의 범위의 값을 구한 dp의 값으로 해결한다면 된다.)

코드

class Solution {
    public int[] solution(int e, int[] starts) {  
        int[] answer = new int [starts.length];
        int[] dp = new int[e+1];
        int[] dp2 = new int[e+1];
        int min =starts[0];
        //약수 찾기
        dp2[1]= 1;
        for(int i=2;i<=e;i++){
            int count =0;
            for (int j = 1; j<= e; j++) {            
                if (j * i > e) break;                
                dp[i*j]++;
            }           
            dp2[i]= i;    
        }
      
        // 가장 큰수 찾기             
        for(int i=e-1;i>=1;i--){
            if(dp[i]>=dp[dp2[i+1]]){
                dp2[i] = i;
            }else{
                dp2[i] = dp2[i+1];
            }                
        }
        
     
       
        //리턴
         for(int i=0;i<starts.length;i++){
            answer[i] = dp2[starts[i]];
        }
       
        return answer;
    }
   
}