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

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

프로그래머스

문제를 이해하기가 까다로운 문제였습니다. 결국 문제 해결하는데 있어서 시간이 오래 걸려 과정을 참고한 코드지만 포인트만 잘 집어낸다면 문제를 빠르게 해결할 수 있을 것입니다.

 

고찰 과정

단순하게 억억단표를 만들어서 이중 반복문을 통해서 최댓값을 도출하기에는 e의 최댓값이 500만이므로 500 x 500의 표를 만들어서 보기에는 1억이 훨씬 넘는 연산량이 필요하기 때문에 이중 반복문을 사용할 수가 없습니다.

 

그래도 일단은 빈도수 정보가 필요하기에 우선 다음과 같은 배열 정보를 만듭니다.

freqs 배열: 억억단표에서 1부터 e까지 각 숫자가 나타난 빈도수

 

이 배열을 활용해서 억억단표에서 각 숫자가 나타난 빈도수 정보를 전부 저장합니다.

정보를 저장하고 freqs 배열을 자세히 살펴보면 1부터 e까지 각 숫자가 나타나는 빈도수가 오름차순 형식으로 나오는 것을 확인할 수가 있습니다. 이를 활용해서 e부터 1까지 역순으로 돌아가며  freqs의 특정 지점에서의 나타난 최대 빈도수를 가진 숫자의 정보를 담기만 한다면 답을 쉽게 추출할 수가 있습니다. 여기서 한가지 주목해야하는 점은 억억단표에서 s이상 e이하의 수라는 의미는 행과 열 범위에서가 아닌 억억단표 내의 값에서의 특정 범위를 말하기 때문에 1부터 s-1까지의 출현 빈도수는 아무런 영향이 없습니다.

 

최대 빈도수를 가진 값의 정보를 저장하기 위해서 다음과 같은 배열을 추가로 만들어줍니다.

maxValues 배열: 특정 값에서의 출현 빈도가 가장 많은 수

 

freqs배열, maxValues 두 배열을 활용해서 특정 값에서의 최대 빈도수를 가진 값을 출력하면 됩니다.

 

---

코드

/**
억억단 표 내에서 s 이상 e 이하의 존재하는 수 중 출현 횟수가 가장 많은 숫자를 리턴해야한다.
**/
class Solution {
    public int[] solution(int e, int[] starts) {
        int startsLen = starts.length;
        int[] answer = new int[startsLen];
        int[] freqs = new int[e + 1]; // 특정 값이 출현하는 빈도수 정보
        int[] maxValues = new int[e + 1]; // 특정 값에서의 출현 빈도가 가장 많은 수
        
        // 억억단표에서 특정값이 출력되는 빈도수를 모두 저장하기
        for (int i = 1; i <= e; ++i) {
            for (int j = i; j <= e; j += i) {
                ++freqs[j];
            }
        }
        
        // e부터 1까지 거꾸로 탐색하여 최대 빈도 및 최대 빈도를 나타내는 값의 정보를 등록한다.
        // 1부터 e까지 점점 커질수록 출현 빈도가 많아져 오름차순이 보장되기 때문에 거꾸로 탐색하여 최대값 정보를 도출한다.
        // 거꾸로 탐색을 함으로써 특정 지점부터 e까지 최대 빈도수를 가진 값의 정보를 출력할 수 있다.
        int maxFreq = 0;
        int maxValue = 0;
        for (int i = e; i >= 1; --i) {
            if (freqs[i] >= maxFreq) {
                maxFreq = freqs[i];
                maxValue = i;
            }
            
            maxValues[i] = maxValue;
        }
        
        // 결과
        for (int i = 0; i < startsLen; ++i) {
            answer[i] = maxValues[starts[i]];
        }
        
        return answer;
    }
}