[백준/BOJ] 2910번 빈도 정렬 (C++)

www.acmicpc.net/problem/2910

2910번: 빈도 정렬

조금 까다로웠던 정렬 문제입니다. (다시 풀기)

빈도 수를 기준으로 내림차순 정렬하고, 빈도 수가 같다면 원래 순서를 유지해야하는 문제입니다. 예를들어,

4 2

2 1 2 1 이 입력값이라면 출력값은 2 2 1 1 이 나와야 합니다.

이를 구현하기 위해서 두 개의 map을 사용했는데, 각각 입력값의 빈도수, 입력값의 순서를 저장합니다. 빈도 수를 저장한 map을 벡터로 값을 옮기고, cmp 함수를 만들어 입력값을 저장한 map을 이용해주었습니다. 

 

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

map<int, int> order; // 순서를 저장할 map 

int cmp(pair<int, int> a, pair<int, int> b) {
	if(a.first == b.first) return order[a.second] < order[b.second]; // 원래 순서 유지
	
	return a.first > b.first; // 빈도 수 기준 내림차순
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, c;
	cin >> n >> c;
	map<int, int> m;
	map<int, int>::iterator it;
	vector<pair<int, int > > v;
	vector<int> answer;
	
	for(int i = 0; i < n; i++) {
		int num;
		cin >> num;
		m[num]++;
		if(order[num] == 0) order[num] = i + 1; // 순서 저장 
	}
	
	for(it = m.begin(); it != m.end(); it++) {
		v.push_back( {it -> second, it -> first} );
	} 
	
	sort(v.begin(), v.end(), cmp);
	
	for(int i = 0; i < v.size(); i++) {
		for(int j = 0; j < v[i].first; j++) {
			answer.push_back(v[i].second);
		}
	}
	
	for(int i = 0; i < answer.size(); i++) {
		cout << answer[i] << " ";
	}
}