JAVA 백준 2910 빈도 정렬 (정렬, 해시와 맵)

 

 

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

 

---

문제

1. 첫째 줄에 메시지의 길이 N과 C ( 1 <= N <= 1000, 1 <= N <= 1000000000 ) 가 입력된다.
2. 둘째 줄에 길이가 N인 수열이 주어진다.
3. 둘째 줄에 적힌 수열에서 등장하는 횟수를 내림차순으로 정렬하여 해당 수를 등장 횟수만큼 출력한다. 이 때 등장하는 횟수가 같다면 수열에서의 위치를 기준으로 먼저 나온 것을 앞에 넣어 출력한다.

---

 

 

 

정답 코드

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));

        StringTokenizer st = new StringTokenizer(br.readLine());

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

        st = new StringTokenizer(br.readLine());

        Map<Integer, Integer> numbers = new HashMap<>();
        ArrayList<Integer> list = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());
            numbers.put(num, numbers.getOrDefault(num, 0) + 1);
            if (!list.contains(num)) {
                list.add(num);
            }
        }

        Integer[] temp = numbers.values().toArray(new Integer[0]);
        Arrays.sort(temp, Collections.reverseOrder());

        StringBuilder sb = new StringBuilder();

        int index = 0;

        for (int i = 0; i < temp.length; i++) {
            while (true) {
                if (Objects.equals(numbers.get(list.get(index)), temp[i])) {
                    for (int k = 0; k < temp[i]; k++) {
                        sb.append(list.get(index)).append(" ");
                    }
                    list.remove(index);
                    index = 0;
                    break;
                } else {
                    index++;
                }
            }
        }

        System.out.println(sb);
    }
}

 

 

해당 수를 얻기 위한 조건만 잘 맞추면 된다.

 

총 두 개의 배열과 한 개의 HashMap을 사용했다.

 

하나의 배열에는 수열에서의 해당 수를 가장 먼저 등장한 수를 기준으로 배열에 삽입했다.

 

HashMap에는 수열에 등장한 수와 해당 수의 등장 횟수를 쌍으로 하여 HashMap에 삽입하도록 한다.

등장 횟수 Value를 배열에 모두 저장하여 등장 횟수를 내림차순으로 정렬.

 

등장 횟수 배열과 HashMap을 비교하여 처음에 만든 등장 순서 배열과 비교하여 출력할 수 있도록 한다.