백준 2910 C++

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

2910번: 빈도 정렬

 

여기서 고민한 점은 결국 빈도수와 숫자가 가장 먼저 나온 index를 저장하는 방식이었다.

set을 쓸까 고민도 했지만 map으로 진행하였다.

map을 사용하는 방법에 대해서 잘 몰랐는데 덕분에 한번 알아보게 되었고

 

아래 코드에서 bin[t] == 0으로 확인하듯이 map에 값이 없으면 0으로 되어 있단 점을 이용해 이미 한번이라도 들어왔는지 확인을 하였다.

 

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

int n, c;
map<int, int> bin;
map<int, int> numIndex;
vector<pair<int, int>> v;

bool binsort(pair<int, int> a, pair<int, int> b)
{
	if (a.second == b.second) {
		return numIndex[a.first] < numIndex[b.first];			//index가 작은게 앞으로 가게 만듦
	}

	return a.second > b.second;			//빈도가 많은게 앞으로 가도록 함.
}

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

	cin >> n >> c;

	for (int i = 1; i <= n; i++) {		//numIndex에 1부터 넣기 위해서 1부터 시작
		int t; cin >> t;
		
		if (bin[t] == 0) {
			numIndex[t] = i;
		}

		bin[t]++;
	}

	for (auto i : bin) {
		v.push_back({ i.first, i.second });		//i.first = 숫자 , i.second = 숫자의 빈도수
	}

	//
	sort(v.begin(), v.end(), binsort);

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