[BOJ/CPP] 빈도 정렬 - 2910번 / C++풀이

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

2910번: 빈도 정렬

정렬 문제이다.

 

숫자 N개를 입력받아서 정렬을 하는 알고리즘을 작성

 

정렬 기준

1. 숫자가 많이 나오는 순서

2. 개수가 같다면 먼저 나온 것이 앞에 있어야 함

 

해당 숫자가 몇번째에 등장하였는지 알 수 있는 값을 넣어준 후 그것을 기준으로 정렬 후 출력한다.

 

map과 pair를 조합하여 풀었다.

 

 

 

해결 방법

1. 숫자를 입력 받아 map 안에 없는 숫자라면 새로 넣어준다.

ex) 3이 5번째에 처음 들어왔다고 예를 들면 [3, 1, 5]

1-1. 있는 숫자라면 개수만 증가시켜준다.

ex) 3이 8번째에 두 번째로 들어왔다면 [3, 2, 5]

2. vector에 옮겨서 위의 정렬 기준에 맞춰 정렬한다. (map은 커스텀 정렬이 안되기 때문에..)

3. 해당 숫자를 개수만큼 출력해주면 끝

 

 

그림의 형태로 map을 만들기 위해 map<int, pair<int,int>> 형태로 선언해준다.

 

처음 들어가는 숫자라면 [n,1,i]로 넣어주고 그게 아니라면 map 의 key값의 첫번째 값만 증가시켜준다.

map <key, pair <int, int>>

 

벡터로 옮겨준 후 정렬을 진행한다.
기본 map이 pair형태로 구성되어있기 때문에 벡터는 pair를 두 개 써서 자료를 온전히 옮길 수 있도록 정의한다.

 

정렬 함수는 잘 생각해서 작성해야한다.

개수가 같지 않다면, 개수가 많은 순서로.

개수가 같다면 먼저 들어온 순서로!

 

전체 코드

      

      

      

    
    

      <cpp />
    
#include <bits/stdc++.h>
using namespace std;

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

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

	map <int, pair <int, int>> mp;

	int n, c; cin >> n >> c;

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

	vector <pair <int, pair<int, int>>> vc(mp.begin(), mp.end());
	sort(vc.begin(), vc.end(), comp);

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