[프로그래머스, JAVA] 억억단을 외우자 - 레벨 3 | 효율성 통과가 어려운 문제

📌 프로그래머스 Level 3 : 억억단을 외우자

레벨 3 치고는 굉장히 쉬워보이지만 파이썬으로 풀면 시간이 너무 빡빡해서 자바로 풀었다.!

📝 내 답안

class Solution {
    public int[] solution(int e, int[] starts) {
        int[] answer = new int[starts.length];
        int[] dic = new int[e+1];
        int[] cnt = new int[e+1];
        dic[1] = 1;
        cnt[1] = 1;
        for(int i=2;i<=e;i++){
            int n = e/i;
            int j = i;
            for(int k=1;k<=n;k++){
                dic[j] += 1;
                j += i;
            }   
        }
        
        // e부터 1까지 각각 최대 출연 번호 저장
        int v = 0;
        for(int i=e;i>=1;i--){
            if(dic[i] >= v){
                v = dic[i];
                cnt[i] = i;
            } else{
                cnt[i] = cnt[i+1];
            }
        }
        
        for(int i=0;i<starts.length;i++){
            answer[i] = cnt[starts[i]];
        }
        return answer;
    }
}

세그먼트 트리를 사용하면 더 효율성 있게 풀 수 있다.

조금 더 생각해보고 세그먼트 트리를 잘 활용해서 파이썬으로도 풀어봐야겠다.