[백준/Java] 2910번 빈도 정렬

-Code

import java.io.*;
import java.util.*;

public class BOJ2910 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int len = Integer.parseInt(st.nextToken());
        int maxNum = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        // 메모리 관리를 위한 map 셋팅 (입력이 1000개로 한정되므로)
        Map<Integer, Integer> numMinIdx = new HashMap<>();
        Map<Integer, Integer> numCnt = new HashMap<>();
        for (int i = 0; i < len; i++) {
            int num = Integer.parseInt(st.nextToken());
            int saveIndex = numMinIdx.getOrDefault(num, Integer.MAX_VALUE);
            numMinIdx.put(num, Math.min(saveIndex, i));
            numCnt.put(num, numCnt.getOrDefault(num, 0) + 1);
        }
        ArrayList<Integer> nums = new ArrayList<>(numCnt.keySet());
        // 정렬
        nums.sort(((o1, o2) -> {
            // 갯수가 많으면 앞으로
            if (numCnt.get(o1) != numCnt.get(o2)) {
                return numCnt.get(o2) - numCnt.get(o1);
            }
            // 갯수가 같은 경우 index가 작으면 앞으로
            return numMinIdx.get(o1) - numMinIdx.get(o2);
        }));
        // 출력
        StringBuilder sb = new StringBuilder();
        for (int num : nums) {
            int loop = numCnt.get(num);
            // 출현 횟수에 따른 저장
            for (int i = 0; i < loop; i++) {
                sb.append(num).append(" ");
            }
        }
        System.out.println(sb);
    }
}

처음에 map을 사용 안 하고 배열로 했더니 메모리 초과로 틀렸습니다. map으로 하나 배열로 하나 메모리는 최악의 경우 10억 개라 괜찮은 줄 알았지만 범위 말고 입력 최대 개수가 1000개라 결국 최대 1000개의 공간만 필요합니다. 하지만 배열은 입력만큼 쓰는 게 아니라 사용하지 않는 메모리를 차지하게 되므로 메모리 초과가 되어 map으로 해보라는 힌트를 보고 해결했습니다.