[정렬][맵][백준] 2910 빈도 정렬 c++ 구현

목차

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

2910번: 빈도 정렬

문제

 

보시기 전에 참고하면 좋을 것 같습니다..

https://be-senior-developer.tistory.com/9

c++ 입출력 정리와 자주 쓰이는 vector

 

문제를 풀기 전에 알아야 될 점

벡터의 정렬 기준을 정해주는 오퍼레이터

bool cmp(int a, int b) { //정렬기준을 제공
	return a < b;  //앞a가 뒤b보다 작을 경우 true를 반환해서 순서를 유지함 
}

 

 

 

문제 구현 방향 및 풀이

문제 풀이 시 만든 배열

vector<pair<int, int>> v; //정렬을 하기위한 벡터
map<int, int> num_m;   //값에 대한 빈도수를 저장하기 위한 맵
map<int, int> first_m;  //순위를 저장하기 위한 맵

 

값에 대한 빈도수를 저장한 맵과 순위를 저장한 맵을 이용해 벡터에 넣고 정렬 기준을 오퍼레이터에

넣어주고 정렬해 주면 된다.

 

 

코드 구현

#include <iostream>
#include <vector>
#include<algorithm>
#include<map>
using namespace std;

vector<pair<int, int>> v; //정렬을 하기위한 벡터
map<int, int> num_m;
map<int, int> first_m;  //순위를 저장하기 위한 벡터
int a[1004] = { 0 };

bool cmp(pair<int,int> a, pair<int, int> b) { //정렬기준을 제공
	if (a.second == b.second)
		return first_m[a.first] < first_m[b.first];
	return a.second > b.second;
}

int main()
{
	 int N, C, i, j;
	cin >> N >> C;
	for (i = 0; i < N; i++) {
		cin >> a[i];
		num_m[a[i]]++;  //카운트 1증가
		if (first_m[a[i]] == 0)  //처음 나왔을 때만 순위 저장
			first_m[a[i]] = i + 1;
	}
	for (auto k : num_m)
		v.push_back({k.first, k.second});  //값과 빈도 벡터에 넣어준다
	sort(v.begin(), v.end(), cmp);  //정렬기준을 바탕으로 정렬

	for (auto k : v) {
		for (j = 0; j < k.second; j++) {
			cout << k.first << " ";   //빈도만큼 각 값을 출력해 준다.
		}
	}
		

}