[BOJ/백준] 2910 빈도 정렬 (S3)

문제

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

풀이

문제를 보면 값에 대한 빈도수를 저장해서 정렬해야되기 때문에 HashMap 생각했고, 빈도수가 같은 경우에는 먼저 등장한 숫자가 앞으로 나오도록 해야 하므로 순서를 지정할 수 있는 LinkedHashMap을 사용했다.

 

<숫자, 빈도수>를 가져야 하기 때문에 <Integer, Integer>를 갖는 LinkedHashMap인 map을 생성하여 문자열을 끊어서 입력받았다.

입력받은 문자열을 정수로 변환해서 map에 넣어줄건데, map에 해당 값(key)이 있다면 value+1을 하여 다시 저장해주고, key가 없다면 새로운 key값과 value에 1을 저장하였다.

 

그리고 map의 key들을 ArrayList에 저장하여 Comparator를 사용하여 map의 key에 대한 value(빈도수)를 기준으로 내림차순 한다.

 

정렬된 list(ArrayList)를 Iterator를 통해 StringBuilder sb에 저장하고 출력한다.

Iterator : List, Set, Map 등에서 값을 가져오거나 삭제할 때 사용한다.

Code

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());  // 문자열을 끊어서 받기 위한 StingTokenizer
        int n = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        // LinkedHashMap 생성 - 값에 대한 빈도수 저장 & 순서 보장
        HashMap<Integer, Integer> map = new LinkedHashMap<>();  // <입력값, 개수>
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(st.nextToken());  // 문자열로 받은 값을 숫자로 변환
            // map 안에 num이 있으면 기본 값에 +1을 하여 저장
            // 없으면 새로 값을 추가
            if (map.containsKey(num)) {
                map.put(num, map.get(num)+1);  // 있으면 map에서 num에 대한 값을 가져와서 +1
            } else {
                map.put(num, 1);  // 새로운 값이 들어가므로 value:1
            }
        }

        // 키를 모두 ArrayList에 저장
        List<Integer> list = new ArrayList<>(map.keySet());  // map의 key들을 저장

        // Comparator를 사용하여 list의 키의 값들을 내림차순으로 정렬
        Collections.sort(list, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return map.get(o2).compareTo(map.get(o1));  // list의 o1을 map의 키값으로 한 value값을(숫자의 개수) 비교
            }
        });

        StringBuilder sb = new StringBuilder();  // 결과값 출력

        Iterator<Integer> it = list.iterator();
        while (it.hasNext()) {
            Integer e = it.next();
            for (int i = 0; i < map.get(e); i++) {  // e에 대한 value 값만큼 반복 -> 값의 횟수만큼 반복
                sb.append(e + " ");
            }
        }
        System.out.println(sb);
    }
}