[백준/2910] 빈도 정렬 - JAVA

📌 문제

알고리즘 분류 : 정렬
난이도 : 실버3
출처 : 백준 - 빈도 정렬

🦧 문제 풀이 접근

숫자, 순서, 빈도수 배열을 담은 Class를 생성한다.
객체 Arraylist를 생성 한 후 Comparator을 이용해 정렬 한다.

빈도가 높은 것이 앞으로 가게 정렬한다.
빈도가 같을 경우 순서가 먼저인 것을 앞으로 가게 정렬한다.

💻 code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int N = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        Map<Integer,Message> messages = new HashMap<>();
        st = new StringTokenizer(br.readLine()," ");
        for(int i=0;i<N;i++) {
            int num = Integer.parseInt(st.nextToken());
            if(messages.isEmpty())
                messages.put(num,new Message(num,1,0));
            else if(messages.containsKey(num))
                messages.put(num,new Message(num, messages.get(num).frq+1, messages.get(num).order));
            else
                messages.put(num,new Message(num,1,messages.size()));
        }
        ArrayList<Message> messageArrayList = new ArrayList<>(messages.values());
        Collections.sort(messageArrayList, new Comparator<Message>() {
            @Override
            public int compare(Message o1, Message o2) {
                if(o1.frq==o2.frq)
                    return o1.order - o2.order;
                return o2.frq - o1.frq;
            }
        });
        for(int i=0;i<messageArrayList.size();i++) {
            for(int j=0;j<messageArrayList.get(i).frq;j++) {
                sb.append(messageArrayList.get(i).num).append(" ");
            }
        }
        System.out.println(sb);
    }
    static class Message {
        int num;
        int frq;
        int order;
        Message(int num,int frq, int order) {
            this.num =num;
            this.frq = frq;
            this.order = order;
        }
    }
}

🥇 결과

🎓 느낀점

map, arraylist를 적절히 사용하면 메모리, 시간을 절약할 수 있다.