[240226] 알고리즘 리부트 17일차 - 백준 2910 자바

[Part1-Chapter05-Clip07]

- 백준 2910 빈도 정렬

 

자료구조로 고민이 많았던 문제이다. 일단 시간제한이 1초로 정해져있었고 최대 들어올 수 있는 숫자가 십억이었기 때문에 카운트 배열을 쓸 수는 없다고 생각했다. 이차원 배열 사용하는 것을 고려하려다가 반복문을 여러번 돌면 시간 제한이 걸릴 것 같아 해시맵을 사용하고자 했다. 초반에는 중첩된 해시맵을 사용하려다가 익숙하지 않아 자꾸 꼬이는 바람에 해시맵을 두개로 분리하여 사용했다. 하나는 빈도를 입력하는 해시맵(map)이고 하나는 기존 순서를 입력하는 해시맵(order)이다. 

정렬하는 부분에서는 일단 존재하는 키를 집합으로 꺼내서 순서대로 정렬하는 것이었다. 빈도값인 value가 큰 경우 먼저 위치하도록 역순으로 처리했다. 애를 먹었던 한 가지는 빈도가 같은 경우의 순서를 정렬하는 것이었다. 해시맵을 하나 더 만들어서 순서를 정해주겠다는 것은 좋은 접근이었으나 Compartor에서 어떻게 써야 할지 모르겠어서 한참 고민했다. (진짜 얼마나 돌아왔는지 모르겠다.. ) 결론만 정리하자면 order 맵의 등장 순서를 기준으로 o1과 o2를 정렬해라 라는 의미로 사용한 것이다.

• 빈도수가 같은 경우: order.get(o1) - order.get(o2)으로 등장 순서대로 정렬
• 빈도수가 다른 경우: map.get(o2) - map.get(o1)으로 빈도수 내림차순으로 정렬

 

package BaekJoon.sort;

import java.util.*;

public class BJ2910 {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int c = sc.nextInt();

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

        for (int i = 0; i < n; i++) {
            int thisNum = sc.nextInt();
            //System.out.println("이번 숫자는: " + thisNum);
            if (map.containsKey(thisNum)) {
                //System.out.println("존재해요");
                int thisValue = map.get(thisNum);
                map.replace(thisNum, thisValue, thisValue + 1);
            } else {
                //System.out.println("없어요");
                map.put(thisNum, 1);
            }

            if (!order.containsKey(thisNum)) {
                //System.out.println(thisNum+"의 순서는: "+i);
                order.put(thisNum, i);
            }
        }

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


        keySet.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                if (map.get(o1) == map.get(o2)) {
//                    System.out.println("o1의 키: "+o1);
//                    System.out.println("o2의 키: "+o2);
//                    System.out.println("o1의 값: "+map.get(o1));
//                    System.out.println("o2의 값: "+map.get(o2));
//                    System.out.println("o1의 순서: " +order.get(o1));
//                    System.out.println("o2의 순서: " + order.get(o2));
                    return order.get(o1) - order.get(o2);
                } else {
                    return map.get(o2) - map.get(o1);
                }
            }
        });

        StringBuilder sb = new StringBuilder();


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

    }
}