2910번: 빈도 정렬

문제

메시지를 이루는 N개의 숫자가 주어집니다. 이 수열을 빈도수가 높은 순서대로 정렬하여 출력하는 문제입니다. 단, 등장하는 빈도수가 같다면 수열에서 먼저 등장한 숫자가 앞에 와야 합니다.

• 입력:
  • 첫째 줄: 메시지의 길이 N과 숫자의 최댓값 C
  • 둘째 줄: 수열을 이루는 N개의 정수
• 출력: 조건에 맞게 정렬된 수열

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

풀이

숫자의 등장 빈도수와 최초 등장 위치(인덱스)라는 두 가지 정보를 저장하고, 이를 기준으로 다중 조건 정렬을 수행하는 문제입니다.

1. 빈도수 및 최초 등장 위치 기록: 데이터를 관리하기 위해 두 개의 HashMap을 사용합니다.
   • map1: 각 숫자가 몇 번 등장했는지 빈도수를 누적하여 저장합니다. (getOrDefault 활용)
   • map2: 각 숫자가 처음 등장한 인덱스만 저장합니다. 한 번 저장된 인덱스는 덮어쓰지 않도록 putIfAbsent 메서드를 활용합니다.
2. 커스텀 정렬 (Comparator): 수열이 담긴 list를 정렬하기 위해 Collections.sort()와 람다식을 사용합니다.
   • 두 숫자 x1과 x2의 빈도수(map1.get)가 같다면, 최초 등장 인덱스(map2.get)를 비교하여 값이 작은 쪽이 앞으로 오도록 오름차순 정렬(map2.get(x1) - map2.get(x2))합니다.
   • 빈도수가 다르다면, 빈도수가 큰 쪽이 앞으로 오도록 내림차순 정렬(map1.get(x2) - map1.get(x1))합니다.
3. 정렬이 완료된 리스트를 순서대로 출력합니다.

코드

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));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       StringTokenizer st = new StringTokenizer(br.readLine());
       int n = Integer.parseInt(st.nextToken());
       int c = Integer.parseInt(st.nextToken());

       Map<Integer, Integer> map1 = new HashMap<>(); // 빈도수 저장 맵
       Map<Integer, Integer> map2 = new HashMap<>(); // 최초 등장 인덱스 저장 맵

       List<Integer> list = new ArrayList<>();
       st = new StringTokenizer(br.readLine());
       
       for (int i = 0; i < n; i++) {
          int x = Integer.parseInt(st.nextToken());
          list.add(x);
          
          // 빈도수 누적
          map1.put(x, map1.getOrDefault(x, 0) + 1);
          // 최초 등장 인덱스 기록 (이미 존재하면 무시)
          map2.putIfAbsent(x, i);
       }

       // 다중 조건 커스텀 정렬
       Collections.sort(list, (x1, x2) -> {
          // 1. 빈도수가 같다면 먼저 등장한 순서대로 (오름차순)
          if (map1.get(x1).equals(map1.get(x2))) {
             return map2.get(x1) - map2.get(x2);
          }
          // 2. 빈도수가 다르다면 많이 등장한 순서대로 (내림차순)
          return map1.get(x2) - map1.get(x1);
       });

       // 정렬된 리스트 출력
       for (int x : list) {
          bw.write(x + " ");
       }

       bw.flush();
       bw.close();
       br.close();
    }
}

알고리즘 분류

정렬 (Sorting), 자료구조, 해시를 사용한 집합과 맵 (Hash Map)