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

문제 설명

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

문제 풀이

• 문제의 핵심은 start <= n <= end 인 n이 억억단에 등장하는 횟수는 n의 약수의 개수와 같다는 것이다.
• start <= n <= end인 n의 약수를 매번 구하는 것은 시간초과가 발생하므로 일차원 배열(dp)에 저장한다.
• 1 ~ end 사이의 모든 수들에 대한 약수를 구하여 저장하고 약수의 갯수의 역순, n의 번호의 정순으로 정렬한다.
• starts 배열의 s가 정해지면 위의 정렬한 배열을 처음부터 탐색하여 처음 n >= s가 되는 n을 찾아서 출력한다.

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public Point[] dp;

    public class Point {
        int n, c;
        public Point(int n, int c) {
            this.n = n;
            this.c = c;
        }
    }

    public void calDp(int e) {
        dp = new Point[e];

        for (int i = 1; i <= e; i++) {
            dp[i - 1] = new Point(i, 1);
        }
        //각 수의 약수의 갯수 모두 구하기
        for (int i = 2; i <= e; i++)
            for (int j = 1; j <= e / i; j++)
                dp[i * j - 1].c++;

        //c 역순, n 정순으로 정렬
        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.n > o2.n) return 1;
                    else if (o1.n < o2.n) return -1;
                    else return 0;
                }
            }
        });
    }

    public int[] solution(int e, int[] starts) {
        int[] res = new int[starts.length];
        calDp(e);

        for (int i = 0; i < starts.length; i++) {
            int s = starts[i];
            for (int j = 0; j < e; j++) {
                if (dp[j].n >= s) {
                    res[i] = dp[j].n;
                    break;
                }
            }
        }
        return res;
    }
}