[백준] 실버3-빈도 정렬 C++ 2910번

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

 

// map 배열을 key가 아닌 value를 기준으로 정렬하고 싶다면,

// vector에 넣어서 (custom operator 기준으로) sort를 해야한다.

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

int n, c;
map<int, pair<int, int>> mp;	// key, {count, index}

bool cmp(pair<int, pair<int, int>>& a, pair<int, pair<int, int>>& b)
{
	if (a.second.first == b.second.first)
		return a.second.second < b.second.second;
	return a.second.first > b.second.first;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> c;
	for (int i = 0; i < n; i++)
	{
		int temp;
		cin >> temp;
		if (mp.find(temp) != mp.end())
		{
			mp[temp].first++;
		}
		else
			mp.insert({ temp,{1,i} });
	}

	vector<pair<int, pair<int, int>>> v(mp.begin(), mp.end());

	sort(v.begin(), v.end(), cmp);

	for (auto it : v)
	{
		int cnt = it.second.first;
		while (cnt--)
		{
			cout << it.first << ' ';
		}
	}

	return 0;
}