2910_빈도정렬

-등장 횟수가 같다면 먼저 입력된 값이 먼저 출력되어야 한다. -> sort함수의 compare 조건을 추가로 주어야한다.

-자료구조는 map 사용하는 이유 : 요소가 1~77까지 가능하다 하면 등장하지 않는 요소도 있기 때문에 탐색을 빠르게 할 수 있는 map을 사용하는 것이 좋다

 

mp[요소] =등장횟수
mp_first[요소]= 첫 등장 위치

-map을 key값이 아닌 value값을 기준으로 sort 함수를 사용하는 법
1. map을 vector로 이동 

2. vector를 정렬시킴

for(auto a:mp){
		v.push_back(make_pair(a.second,a.first)); //a.second는 등장횟수, a.first는 요소값 
	}
	
sort(v.begin(),v.end(),compare);

vector를 first기준으로 정렬할때 값이 같다면 map_first[vector.second]값이 작은 것이 먼저 정렬되도록 한다.
출력은 vecotr에 저장된 순서대로 vector.first만큼 출력한다.

bool compare(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; //오름차순 
}

-소스코드

#include<bits/stdc++.h>
using namespace std;
int n,c,num;
vector <pair<int,int> > v;
map <int,int> mp,mp_first;
bool compare(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(void){
	cin >> n >>c;
	for(int i=0;i<n;i++){
		cin>> num;
		mp[num]++;
		if(mp_first[num]==0)
			mp_first[num]=i+1;
	}
	
	for(auto a:mp){
		v.push_back(make_pair(a.second,a.first)); //a.second는 등장횟수, a.first는 요소값 
	}
	
	sort(v.begin(),v.end(),compare);

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

 

참고:

https://unluckyjung.github.io/cpp/2020/05/07/Sort_map_by_value/