빈도 정렬 - 2910

문제

풀이

package Beakjoon_zaqabi;


import java.util.*;

// 빈도 정렬 - S3
// 1순위 갯수가 많으면 젤앞에
// 2순위 갯수가 같으면 --> 먼저 나온 순으로
public class ex2910 {

    static int n,m;
    static Integer[] arr;
    public static void solution(){

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

        for(int x : arr) map.put(x,map.getOrDefault(x,0)+1);

        // List 에다가 map 을 담아서 내림차순 정렬
        ArrayList<Integer> list = new ArrayList<>(map.keySet());
        // (저장 순서를 지키면서 크기별로) value 내림차순 정렬
        Collections.sort(list, new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                //list.get(b) 와 list.get(a)의 위치가 바뀌면 오름차순이 된다.
                return Integer.compare(map.get(b), map.get(a));
            }
        });

        //출력
        for(int x : list){
            for(int i=0; i<map.get(x); i++){
                if(x>0){
                    System.out.print(x + " ");
                }
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n=sc.nextInt();
        m=sc.nextInt();

        arr=new Integer[n];
        for(int i=0; i<n; i++){
            arr[i]=sc.nextInt();
        }
        solution();
    }
}

문제를 보자마자 HashMap으로 풀어야겠다는 생각을 했다. 근데 이 문제에서 요구하는 것은 value값이 같을 때 먼저 입력받은 key를 출력하라고 제시했다. 그래서 LinkedHashMap이라는 자료구조를 사용했다. LinkedHashMap의 장점은 저장되는 순서를 기억한다는 점이다. 그래서 LinkedHashMap에 저장하고 내림차순으로 저장하여 입력순서를 기억하면서 value의 크기별로 저장되게 하였다.

HashMap을 오름차순 , 내림차순 정렬하는 법

1. 해당 map.keySet()을 ArrayList인 list에 담는다

2. Collections.sort에 Commparable을 이용해서 함수오버라이드를 통해서 정렬한다. return에서 map.get()을 했기 때문에 value 정렬이다. 그리고 b를 앞에쓰면 내림차순, a를 앞에쓰면 오름차순 정렬이 된다.

Collections.sort(list, new Comparable<인티저>() {
            @Override
            public int compare(Integer a, Integer b) {
       
                return Integer.compare(map.get(b), map.get(a));
            }
        });