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

Lv.3 억억단을 외우자 : 프로그래머스

문제 설명

영우는 천하제일 암산대회를 앞두고 있습니다. 암산보다는 암기에 일가견이 있는 영우는 구구단을 확장하여 억억단을 만들고 외워버리기로 하였습니다.
억억단은 1억 x 1억 크기의 행렬입니다. 억억단을 외우던 영우는 친구 수연에게 퀴즈를 내달라고 부탁하였습니다.
수연은 평범하게 문제를 내봐야 영우가 너무 쉽게 맞히기 때문에 좀 어렵게 퀴즈를 내보려고 합니다. 적당한 수 e를 먼저 정하여 알려주고 e 이하의 임의의 수 s를 여러 개 얘기합니다. 영우는 각 s에 대해서 s보다 크거나 같고 e 보다 작거나 같은 수 중에서 억억단에서 가장 많이 등장한 수를 답해야 합니다. 만약 가장 많이 등장한 수가 여러 개라면 그 중 가장 작은 수를 답해야 합니다.
수연은 영우가 정답을 말하는지 확인하기 위해 당신에게 프로그램 제작을 의뢰하였습니다. e와 s의 목록 starts가 매개변수로 주어질 때 각 퀴즈의 답 목록을 return 하도록 solution 함수를 완성해주세요.

제한 사항

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

분석

억억단에서 s 보다 같거나 크고, e 보다 같거나 작은 수를 구하고, 그 중 가장 많이 등장한 수를 구하여야 하고, 등장 수치가 같으면 작은 값을 선택한다.

풀이

• e의 범위가 5,000,000 이기 때문에 억억단의 나올 수 있는 가장 큰 수치는 5,000,000 ^ 2이다. 하지만 5,000,000 초과된 값은 우리가 찾아야하는 값이 아님
• 시간을 조금 줄이기 위해 값을 찾을 때 억억단 표의 반만 사용하였음. i * j 를 확인하면서, i == j인 경우 1을 카운트, i != j 인 경우, i * j, j * i 두 가지 방식이 나오기 때문에 2를 카운트
• Map(값, 등장 수치)을 구한 뒤, List에 넣어 등장 수치가 많은 순 (같다면 값이 작은 순)으로 정렬
• starts 배열 값을 확인하면서 List index 0 부터 확인하면서, 값이 s 이상인 것을 찾음

 

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] solution(int e, int[] starts) {
        int size = starts.length;
        int[] answer = new int[size];

        Map<Integer, Integer> map = new HashMap<Integer, Integer>();

        for (int i = 1; i <= e; i++) {
            for (int j = 1; j <= i; j++) {
                long value = i * j;
                if (e < value)
                    break;
                if (i == j) {
                    map.put(i * j, map.getOrDefault(i * j, 0) + 1);
                } else {
                    map.put(i * j, map.getOrDefault(i * j, 0) + 2);
                }
            }
        }

        ArrayList<int[]> list = new ArrayList<int[]>();
        for (int key : map.keySet()) {
            list.add(new int[] { key, map.get(key) });
        }

        list.sort(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] == o2[1])
                    return o1[0] - o2[0];
                return o2[1] - o1[1];
            }
        });

        for (int a = 0; a < size; a++) {
            for (int i = 0; i < list.size(); i++) {
                if (starts[a] <= list.get(i)[0]) {
                    answer[a] = list.get(i)[0];
                    break;
                }
            }
        }

        return answer;
    }
}