[프로그래머스 / Java] - 억억단을 외우자

문제 설명

영우는 천하제일 암산대회를 앞두고 있습니다. 암산보다는 암기에 일가견이 있는 영우는 구구단을 확장하여 억억단을 만들고 외워버리기로 하였습니다.
억억단은 1억 x 1억 크기의 행렬입니다. 억억단을 외우던 영우는 친구 수연에게 퀴즈를 내달라고 부탁하였습니다.
수연은 평범하게 문제를 내봐야 영우가 너무 쉽게 맞히기 때문에 좀 어렵게 퀴즈를 내보려고 합니다. 적당한 수 e를 먼저 정하여 알려주고 e 이하의 임의의 수 s를 여러 개 얘기합니다. 영우는 각 s에 대해서 s보다 크거나 같고 e 보다 작거나 같은 수 중에서 억억단에서 가장 많이 등장한 수를 답해야 합니다. 만약 가장 많이 등장한 수가 여러 개라면 그 중 가장 작은 수를 답해야 합니다.
수연은 영우가 정답을 말하는지 확인하기 위해 당신에게 프로그램 제작을 의뢰하였습니다. e와 s의 목록 starts가 매개변수로 주어질 때 각 퀴즈의 답 목록을 return 하도록 solution 함수를 완성해주세요.

제한사항

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

 

정답 설명

이 문제는 알고리즘의 탈을 쓰고 있는 수학 문제 입니다.

우리가 주목해야 할 것은 특정 수가 억억단에서 등장하는 횟수가 무엇을 뜻하는 지 입니다.

특정 수 e가 억억단의 n단에서 등장한다면, n이 e의 약수라는 뜻입니다. 즉, 특정 수가 억억단에서 등장하는 횟수는 해당 수의 약수의 개수와 같습니다.

 

이제 문제는 다음과 같이 바뀌었습니다.

e 이하 s 이상의 수 중 억억단에서 가장 많이 등장한 수를 반환하세요.

→ e 이하 s 이상의 수 중 약수의 개수가 가장 큰 수를 반환하세요.

 

문제 해결을 위해선 불가피하게 모든 수의 약수의 개수를 기억하고 있어야 합니다.

모든 약수의 개수를 구하고 나서는 특정 수 s 이상의 수 중 가장 약수의 개수가 많은 (여러개라면 그 중 가장 작은) 수를 구해야 합니다. 이는 e 이하의 모든 수를 내림차순으로 확인하여 s 이상의 수 중 가장 약수의 개수가 많은 수를 기억하는 DP 배열을 생성하며 O(n)의 시간 내에 해결할 수 있습니다.

 

소스 코드

import java.util.*;
class Solution {
    public int[] solution(int e, int[] starts) {
        int[] answer = new int[starts.length];
        int[] divCount = new int[e+1];
        int[] maxFreq = new int[e+1];
        int maxIdx = e;
        
        for(int i = 1; i<= e; i++)
            divCount[i] = 1;
        
        for(int i = 2; ; i++){
            if(i > e)
                break;
            for(int j = 1; ; j++){
                if(i * j > e)
                    break;
                divCount[i*j]++;
            }
        }
        
        for(int i = e; i>0; i--){
            if(divCount[i] >= divCount[maxIdx])
                maxIdx = i;
            maxFreq[i] = maxIdx;
        }
      
        
        for(int i = 0; i<answer.length; i++)
            answer[i] = maxFreq[starts[i]];
        
        return answer;
    }
}