[c++] 백준 2910, 빈도 정렬

백준 2910

🌲 문제 요약

메시지에 등장하는 숫자를 빈도 순서대로 정렬하는 문제.

🌲 문제 풀이

맵 mp에 입력받은 숫자 tmp의 빈도 정보를 저장한다. 이때, 어떤 숫자가 처음 등장한 시점의 정보를 저장하기 위해, if (!mp_first[tmp]) 경우에는 mp_first[tmp] = i + 1의 연산을 수행한다.
mp의 값을 v에 저장한 뒤, sort 함수를 통해 정렬한다. 이 과정에서 sort 함수에 사용된 cmp 함수는 내림차순 정렬과 동시에, 같은 빈도의 숫자 정렬을 수행한다.

🌲 주의

mp_first[tmp]의 값을 정하는 과정에서 mp_first[tmp] = i의 연산을 하지 않도록 주의한다.

🌲 코드

#include <bits/stdc++.h>

using namespace std;
int n, c;
map<int, int> mp, mp_first;
vector<pair<int, int>> v;
 
bool cmp(pair<int, int> a, pair<int, int> b) {
	if (a.first == b.first) {
		return mp_first[a.second] < mp_first[b.second];
	}
	return a.first > b.first;
}

int main() {
	cin >> n >> c;
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		mp[tmp]++;
		if (!mp_first[tmp]) mp_first[tmp] = i + 1;
	}
	for (auto i : mp) v.push_back({i.second, i.first});
	sort(v.begin(), v.end(), cmp);
	for (auto i : v) {
		for (int j = 0; j < i.first; j++) {
			cout << i.second << ' ';
		}
	}
	cout << '\n';
	
	return 0;
}