[알고리즘] 백준 - 빈도 정렬

백준 - 빈도 정렬

내 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;

public class baekjoon_2910 {

    static int N, C;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        N = Integer.parseInt(inputs[0]);
        C = Integer.parseInt(inputs[1]);
        inputs = br.readLine().split(" ");
        LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();
        arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(inputs[i]);
            if (map.containsKey(arr[i])) {
                map.put(arr[i], map.get(arr[i]) + 1);
            } else {
                map.put(arr[i], 1);
            }
        }
        ArrayList<Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
        list.sort(Entry.comparingByValue(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 < o2 ? 1 : o1 == o2 ? 0 : -1;
            }
        }));

        for (Entry<Integer, Integer> keyVal : list) {
            for (int i = 0; i < keyVal.getValue(); i++) {
                System.out.print(keyVal.getKey() + " ");
            }
        }
    }
}

빈도수를 세어야하니 맵을 써야겠다고는 생각했는데, 예전 파이썬에서도 키나 밸류를 기준으로 정렬하는 부분에 약했다.

우선 만약 같은 빈도수라면 들어온 순서대로 정렬해야하니 LinkedHashMap을 썼다. LinkedhashMap은 순서를 유지해준다. 만약 파이썬이었으면 3.7이상부터 딕셔너리에서 키들의 순서를 유지 해준다.

map을 다룰때, Entry들의 list를 받고, 그 list를 comparingByValue하면 Value에 의해 정렬을 할 수 있다.

내 풀이 (파이썬)

from collections import defaultdict

N, C = list(map(int, input().split()))
arr = list(map(int, input().split()))

num_dict = defaultdict(int)
for i in range(len(arr)):
    num_dict[arr[i]] += 1

freq_dict = defaultdict(int)
key_val_list =  list(num_dict.items())

key_val_list.sort(key = lambda x: (-x[1]))
for key_val in key_val_list:
    for _ in range(key_val[1]):
        print(key_val[0], end = " ")

파이썬에서는 이렇게 간단하다...