[백준 2910 with JAVA] 빈도 정렬

 

https://www.acmicpc.net/problem/2910

---

📝 문제 설명

정수들을 입력받아 빈도수가 가장 많은 순서대로 출력하면 된다.
이때 빈도수가 같은 경우에는 먼저 입력받은 정수가 먼저 출력되어야 한다.

✨ 제출 코드

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

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

        int N = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

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

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int key = Integer.parseInt(st.nextToken()); 
            map.put(key, map.getOrDefault(key, 0) + 1);
        }

        List<Integer> lst = new ArrayList<>(map.keySet());

        Collections.sort(lst, new Comparator<Integer>(){
            @Override
            public int compare(Integer a, Integer b){

                return Integer.compare(map.get(b), map.get(a));
            }
        } );

        for (Integer element : lst) {
            for (int i = 0; i < map.get(element); i++) {
                sb.append(element + " ");
            }
        }
        
        System.out.println(sb);        
    }
}

 

✌️ 코드 설명

먼저 정수들을 입력받으면 어떤 정수가 몇 번 입력되었는 지를 기록하기 위해서 Map을 사용했다.

처음에는 그냥 HashMap을 사용했는데 문제에서 등장하는 횟수가 같다면, 먼저 나온 것이 앞에 있어야 한다고 했기 때문에 순서를 고려하고자 LinkedHashMap을 사용했다.

Map에 저장할 때는 <입력받은 정수, 빈도수 > 형태로 저장했으며 getOrDefault를 사용해서 해당 키가 map에 없으면 0, 있으면 1을 증가하는 형태로 진행했다.

그리고 키셋으로 리스트를 만들어 이들을 정렬해 주었다.

정렬을 진행할 때는 map의 value값들로 비교를 해서 내림차순으로 정렬했다.

그 후 리스트를 순회하며, 각각 해당 키 값을 빈도수만큼 출력해 주었다.

♨️ 마무리

📌 HashMap vs LinkedHashMap

순서	순서 없음	입력 순서 또는 접근 순서 보장
내부 구조	해시 테이블	해시 테이블 + 연결 리스트
성능	빠름 (O(1) 시간 복잡도)	HashMap보다 약간 느림 (순서 보장 덕분)
사용 예시	순서가 중요하지 않은 경우	순서가 중요한 경우, 캐시 구현 시 등

🤼‍♀️ 정렬

Collections.sort(lst, new Comparator<Integer>(){
    @Override
    public int compare(Integer a, Integer b){
        return Integer.compare(map.get(b), map.get(a));
    }
});

Collections.sort(lst, (a, b) -> Integer.compare(map.get(b), map.get(a)));

 

익명 클래스를 사용하여 정렬을 진행했지만 람다식으로도 할 수 있다.