[백준] C++ 2910번 빈도정렬

이 문제는 등장하는 빈도순대로 정렬하는 문제이다.

자주 등장하면 앞에 나오고 만약 등장 횟수가 같으면 먼저 등장한 숫자를 먼저 출력한다.

 

문제풀이방법

1. hashMap에 숫자의 등장횟수와 등장순서를 저장한다.

2.등장횟수와 등장순서에 따라 정렬한다.

3.정렬된 순서에 따라 출력한다.

 

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>

using namespace std;

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;//먼저 나온 순서대로 출력
	}
	else
	{
		return a.second.first > b.second.first;
	}
}

int main(void)
{
	unordered_map<int, pair<int, int>> hashMap;

	int N = 0;
	int M = 0;
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		int num = 0;

		cin >> num;
		
		hashMap[num].first++;

		if (hashMap[num].first == 1)//만약 처음 나왔다면?
		{
			hashMap[num].second=i;
		}
	}
	vector<pair<int, pair<int, int>>> V(hashMap.begin(), hashMap.end());
	sort(V.begin(), V.end(), cmp);

	for (int i = 0; i<V.size(); i++)
	{
		for (int j = 0; j<V[i].second.first; j++)
		{
			cout << V[i].first<<" ";
		}
	}
	return 0;
}