문제

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

---

입력

e와 s의 목록 starts

---

출력

각 퀴즈의 답 목록

---

풀이

제한조건

• 1 ≤ e ≤ 5,000,000
• 1 ≤ starts의 길이 ≤ min {e,100,000}
• 1 ≤ starts의 원소 ≤ e
• starts에는 중복되는 원소가 존재하지 않습니다.

접근방법

단순 구현으로 해결했다.
원래는 약수의 개수로 접근하는 문제인듯함

starts의 길이만큼 계속하여 등장 빈도를 계산할 수 없기 때문에 한 번만 미리 다 구한다.

그 다음 정렬을 통해서 가장 많이 등장한 순, 동일한 빈도로 등장했다면 더 작은 수를 기준으로 정렬한다.

그 다음 starts의 원소를 순회하며 조건에 맞는 것들을 찾아 정답으로 기록한다.

---

코드

import java.util.*;
class Pair implements Comparable<Pair>{
    int first;
    int second;
    
    Pair(int a, int b){
        first = a;
        second = b;
    }
    public int compareTo(Pair o){
        if(this.second == o.second)
            return this.first - o.first;
        return o.second - this.second;
    }
}

class Solution {
    public int[] solution(int e, int[] starts) {
        // 각 수의 등장 수를 모두 구한다.
        Pair[] arr = new Pair[e+1];
        for(int i = 0; i <= e; ++i)
            arr[i] = new Pair(i,0);
        
        for(int i = 1; i <= e; ++i)
            for(int j = i; j <=e; j+=i)
                arr[j].second++;
        
        // 등장 빈도가 큰 순, 작은 숫자 우선으로 정렬
        Arrays.sort(arr);
        
        // 정렬되어 있으므로, start보다 arr의 값이 크다면 해당 수가 정답
        int len = starts.length;
        int[] result = new int[len];
        for(int i = 0 ; i < len; ++i){
            for(int j = 0 ; j < e; ++j){
                if(starts[i] <= arr[j].first){
                    result[i] = arr[j].first;
                    break;
                }
            }
        }

        return result;
    }
}