BOJ 2910 : 빈도 정렬

#BOJ  2910 : 빈도 정렬

2910번: 빈도 정렬

#풀이

문제를 보고 pair를 사용하여 숫자에 대해 빈도 수를 저장하게 했다.

입력을 받을 때 벡터 안에 같은 숫자가 있으면 빈도수를 늘리고 아니면 벡터에 추가하게 하여 구현을 했는데.....

sort() 함수를 사용해서 풀었더니 틀렸다. sort() 는 우선순위가 같을 때 순서를 보장해주지 않는다는 것을 알았다.

stable_sort 랑 sort의 차이점은 알았는데 함수를 사용할 때는 생각 하지 못했다.

sort() 함수를 stable_sort() 로 바꾸고 해결하였다.

 

sort : 퀵정렬

stable_sort : 합병정렬

#코드

#include<iostream> // #include<bits/stdc++.h>
#include<vector>
#include<algorithm>
using namespace std;

int n, c;
int flag;
vector<pair<int, int>> v;
bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
	if (a.second > b.second)
		return true;
	return false;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> c;
	for (int i = 0; i < n; i++)
	{
		int num;
		cin >> num;
		flag = 0;
		for (int z = 0; z < v.size(); z++) {
			if (num == v[z].first)
			{
				v[z].second++;
				flag = 1;
				break;
			}
		}
		if (flag)
			continue;
		v.push_back({ num, 1 });
	}
	stable_sort(v.begin(), v.end(), cmp);
	for (int i = 0; i < v.size(); i++) {
		for (int j = 0; j < v[i].second; j++) {
			cout << v[i].first << " ";
		}
	}

	return 0;
}