빈도 정렬

일단 이 문제는

Custom operator가 생각 나야한다고 한다.
(나도 cmp만들기는 했는데 아닌거 같아서 돌아왓음)

또한 map의 특성을 이해하고 활용해야함.

내코드

일단 우선순위 큐가 생각이 나서 pq를 두개를 써서 구현을 해보았는데

이렇게 나왔다. 뭐 당연한 결과이기는 하다 문제를 제대로 이해를 못했던 것이다.

이렇게 할려면 arr이 크기가 10억이여야함.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define endl "\n"

int n, m, v, mx = 0;
vector<pair<int, int>> arr;
priority_queue<pair<int, int>> pq1;
priority_queue<pair<int, int>, vector<pair<int, int>> ,greater<pair<int, int>>> pq2;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;

	// arr.resize();

	for (int i = 1; i <= n; ++i)
	{
		cin >> v;
		++arr[v].first;
		if (arr[v].second == 0) arr[v].second = i;
		mx = max(mx, arr[v].first);
	}

	for (int i = 1; i <= m; ++i)
	{
		if (mx == arr[i].first && arr[i].first != 0)
		{
			pq2.emplace( arr[i].second, i );
		}
		else if (arr[i].first != 0)
		{
			pq1.emplace( arr[i].first, i);
		}
	}

	while (!pq2.empty())
	{
		int a = pq2.top().second; pq2.pop();
		
		for (int i = 0; i < mx; ++i)
			cout << a << " ";
	}

	while (!pq1.empty())
	{
		int b = pq1.top().first;
		int v = pq1.top().second;
		pq1.pop();

		for (int i = 0; i < b; ++i)
			cout << v << " ";
	}
	
	return 0;
}

분석

map이라는 자료구조는

이 특성을 활용해서 if (mp_first[a[i]] == 0)
으로 몇번째로 입력을 받았는지를 체크하고

mp_first[a[i]] = i + 1;로 0이 아닌 + 1한 수를 입력받은 빠다순을 넣은 부분임.

sort할 때는 Custom operator로 정렬을 해줌.

cpp 코드

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
#define endl "\n"

int n, m, a[1004];
vector<pair<int, int>> v;
map<int, int> mp, mp_first;

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()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;

	for (int i = 1; i <= n; ++i)
	{
		cin >> a[i]; mp[a[i]]++;
		if (mp_first[a[i]] == 0) mp_first[a[i]] = i + 1;
	}

	for (auto it : mp)
	{
		v.push_back({ it.second, it.first });
	}

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

	for (auto i : v)
	{
		for (int j = 0; j < i.first; ++j)
		{
			cout << i.second << " ";
		}
	}
	
	return 0;
}