문제링크

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

구현방법

e 이하의 수

s보다 크면서 e이하의 수중에 가장 많이 등장한 수

각 숫자별로 개수체크가 필요하다.

구구단.

각 배열은 n의 각 열의 배수

1 1x2 1x3 1x4 ~ 1x500만

2 2x2 2x3 2x4 -> 2의배수

3 3x2 3x3 3x4 -> 3의 배수

4 4x2 4x3 4x4 -> 4의 배수

5 10 15 20

소수인 경우 -> 2개

1 2 3 6 -> 4개

1 2 4 ->3 개

1 3 -> 2개

1 7 - > 2개

1 2 4 8 -> 4개

...

차례대로 계산을 해보니 각 숫자의 등장 횟수는 약수의 갯수만큼 등장했다.

그렇기 때문에 핵심적으로 생각해야한는 것은 각 약수의 개수를 구하는 것이였고.

약수의 개수를 1~ e 까지 전부 구해놓고 e부터 1까지 내림차순으로 진행하면서 약수 개수가 현재 최대 약수 개수인 max 값보다 크거나 같은 경우 max 값과 maxaddr을 갱신을 진행해서 maxList에 각 위치 까지의 최대addr을 구해놓는다.

• 크거나 같은 경우로 구하는 이유는 만약 최대 등장횟수가 같은 경우 가장 작은 숫자를 도출해내야하기 때문에.

answer는 maxList로 만들어둔 값들을 가져오는 것으로 마무리가 된다.

여담으로 약수 구하는 부분에서 n * sqrt(n)으로 할 경우 O(n^2)이 발생되어 시간초과가 발생했다.

• 이부분이 가장 문제가 되었던 부분이였다. 대체 어떻게 해야하지 하면서 다른분의 질문하기에 남겨놓은 힌트를 보고나서 현재와 같은 코드가 완성되었다.

알고리즘

구현

CODE

class Solution {

    //각 숫자별 개수 계산
    int[] dp;

    int[] maxList;

    public int[] solution(int e, int[] starts) {
        int[] answer = new int[starts.length];
        dp = new int[5000001];
        maxList = new int[5000001];
        dp[1] = 1;

        check(e);
        int max = 0;
        int maxaddr =0;
        for(int idx = e; idx >= 1; idx--){
            //약수개수가 max가 더작은경우 갱신
            if(max <= dp[idx]){
                maxaddr = idx;
                max = dp[idx];
            }
            maxList[idx] = maxaddr;

        }

        //최대 addr이 저장된 maxList에서 값을 꺼내어서 결과 도출
        for(int idx =0; idx <starts.length;idx++){
            answer[idx] = maxList[starts[idx]];
        }

        return answer;
    }

    //약수 개수 구하는 알고리즘
    private void check(int end) {

        for(int i = 2 ; i<=end ; i++){
            for(int j = 1 ; j<=(end/i) ; j++){
                dp[i*j]++;
            }
        }
    }


}