[pro] 프로그래머스 level3 138475 억억단을 외우자 (Java) - dp

[문제]

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

프로그래머스

 

[풀이]

s <= num <= e 인 n이 억억단에 등장하는 횟수는 num의 약수의 개수와 같다. 

예를 들어, 8이 억억단에 등장하는 횟수는 1*8, 2*4, 4*2, 8*1 에 의해 등장할 수 있으므로 8의 약수의 개수인 4번(1,2,4,8)이 되는 것이다.

따라서 숫자와 약수의 개수를 저장해주기 위해 dp 배열을 선언하고 1~e까지의 각 수의 배수에 대해 증가시켜주므로써 약수의 개수를 셀 수 있다.

이후 약수의 개수를 기준으로 내림차순으로 정렬하고, 만약 개수가 같다면 더 작은 수를 반환하도록 Comparator를 새로 정의해 정렬해준다. 정렬한 배열을 처음부터 탐색하여 처음 s<=num이 되는 num을 찾아서 출력한다. 

 

[코드]

 

import java.util.*;

class Solution {
    Point[] dp;
    public int[] solution(int e, int[] starts) {
        int[] answer = {};
        
        dp = new Point[e+1];
        
        for(int i=0; i<=e; i++){
            dp[i] = new Point(i, 0);
        }
        
        //배수 세기
        for(int i=1; i<=e; i++){ 
            for(int j=i; j<=e; j+=i){
                dp[j].c++;
            }
        }
        
        //약수의 개수가 큰 순서대로 정렬
        Arrays.sort(dp, new Comparator<Point>(){
            @Override
            public int compare(Point o1, Point o2){
                if(o1.c < o2.c) return 1;
                else if(o1.c > o2.c){
                    return -1;
                }
                else {
                //작은 숫자 반환
                    if(o1.num > o2.num) return 1;
                    else if(o1.num < o2.num) return -1;
                    else return 0;
                }
            }
        });          
        
        answer = new int[starts.length];
        for(int i=0; i<starts.length; i++){
            for(int j=0; j<=e; j++){
                if(starts[i] <= dp[j].num){
                    answer[i] = dp[j].num;
                    break;
                }
            }
        }
        
        return answer;
    }
    
    static class Point{
        int num, c;
        Point(int num, int c){
            this.num = num;
            this.c = c;
        }
    }
}