[Programmers] 억억단을 외우자 (Java)

1.  문제 링크

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

2.  문제

영우는 천하제일 암산대회를 앞두고 있습니다. 암산보다는 암기에 일가견이 있는 영우는 구구단을 확장하여 억억단을 만들고 외워버리기로 하였습니다.

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

3.  제한사항

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

입출력 예

4.  소스코드

import java.util.*;

class Solution {
    public int[] solution(int e, int[] starts) {
        // 각 수의 등장횟수를 살펴보면 각 수의 약수 개수와 같다
        // 그러므로 1부터 e까지 모든 수의 약수 개수를 미리 구한다
        int[] numbers = findAllNumberDivisorNum(e);
        // 1부터 e까지 각 수를 시작으로 했을 때 등장 횟수가 가장 많은 수를 구한다
        int[] maxNums = findAllMaxNumber(e, numbers);

        int[] answer = new int[starts.length];
        for(int idx = 0; idx < starts.length; idx++) {
            answer[idx] = maxNums[starts[idx]];
        }

        return answer;
    }

	// 1부터 e까지 각 수를 시작으로 했을 때 등장 횟수가 가장 많은 수를 구하는 메서드
    public int[] findAllMaxNumber(int e, int[] numbers) {
        // 등장 횟수 중 가장 큰 수
        int maxNum = 0;
        // 1부터 e까지 각 수를 시작으로 했을 때 등장 횟수가 가장 많은 수
        int[] maxNums = new int[numbers.length];
        
        // e부터 1까지 순회하며 각 수를 시작하는 수로 잡고 그때의 등장 횟수가 가장 많은 수를 구한다
        for(int num = e; num >= 1; num--) {
        	// 만약 이전까지의 가장 큰 등장 횟수보다 현재 수의 등장 횟수가 더 크거나 같다면
            if(numbers[num] >= maxNum) {
            	// 등장 횟수 최댓값을 갱신하고 이 수부터 등장 횟수가 가장 많은 수는 현재 수가 되기 떄문에 maxNums[현재 수]를 현재 수로 값을 설정한다
                maxNum = numbers[num];
                maxNums[num] = num;
            } else { // 등장 횟수 최댓값이 현재 수의 등장 횟수보다 크다면
            	// 이전까지의 등장 횟수가 가장 많은 수가 현재 수에서도 등장 횟수가 가장 많은 수가 되기 때문에 maxNums[현재 수]를 maxNums[바로 이전 수]로 설정한다
                maxNums[num] = maxNums[num + 1];
            }
        }

        return maxNums;
    }

	// 약수 개수를 구하는 메서드
    public int[] findAllNumberDivisorNum(int e) {
    	// 각 수의 약수 개수
        int[] numbers = new int[e + 1];

        // 초기화
        Arrays.fill(numbers, 1);
        numbers[0] = 0;

        // 약수의 개수 구하기
        for(int num = 2; num <= e; num++) {
        	// 2를 약수로 가지는 모든 수의 약수 개수를 1 증가시킨다
            for(int divisor = 1; divisor <= e / num; divisor++) {
                numbers[num * divisor]++;
            }
        }

        return numbers;
    }
}