문제

BOJ 2910, 빈도 정렬

핵심

• 입력의 크기가 $10^3$이라 대략 $O(N^2)$ 이하의 알고리즘을 사용한다. 입력의 수가 작아 구현에 초점을 맞춘다.
• 숫자의 빈도를 조사하여 빈도가 많은 대로 정렬을 하고, 빈도수가 같다면 먼저 나온 숫자를 기준으로 정렬한다. 특정 숫자에 대한 빈도를 알아야 하고, 그 숫자의 인덱스까지 알아야 한다. 해시 자료구조를 이용해 key(숫자)에 대한 value(인덱스와 빈도)를 구해내어 이를 배열로 변환한 뒤 정렬한다.

개선

코드

시간복잡도

• $O(N\times log_2N)$

C++

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

int n, c;
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> c;
	unordered_map<int, pair<int, int>> map; // value: 위치, 반복한 횟수
	for (int i = 0; i < n; ++i) {
		int num;
		cin >> num;
		if (map[num].second == 0)
			map[num].first = i;
		(map[num].second)++;
	}
	vector<pair<int, pair<int, int>>> v;
	for (auto& e : map)
		v.push_back(e);
	sort(v.begin(), v.end(), [](auto& a, auto& b){ 
			if (a.second.second != b.second.second)
				return a.second.second > b.second.second;
			return a.second.first < b.second.first;
	});
	for (auto& e : v) {
		for (int i = 0; i < e.second.second; ++i)
			cout << e.first << ' ';
	}
}

Java

import java.io.*;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

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());
        st = new StringTokenizer(br.readLine());
        HashMap<Integer, Integer> firstIndexMap = new HashMap<>();
        HashMap<Integer, Integer> countMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(st.nextToken());
            firstIndexMap.putIfAbsent(num, i);
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }
        ArrayList<Map.Entry<Integer, Integer>> list = new ArrayList<>(countMap.entrySet());
        list.sort((a, b) -> {
            if (!a.getValue().equals(b.getValue()))
                return b.getValue() - a.getValue();
            return firstIndexMap.get(a.getKey()) - firstIndexMap.get(b.getKey());
        });
        for (var e : list) {
            for (int i = 0; i < e.getValue(); i++) {
                bw.write(e.getKey() + " ");
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }
}