[알고리즘] 백준 2910

백준 2910번 빈도 정렬

해결 과정 요약

숫자의 빈도를 저장하기 위해 unordered_map을 사용한다.
숫자들의 순서를 저장하기 위해 또 unordered_map을 사용한다.
정렬하기위해 커스텀함수를 만든다. 값이 같으면 숫자의 순서로 오름차순, 다르면 빈도로 내림차순 해준다.
map의 value를 기준으로 정렬하기 위해 vector에 map을 다시 담은 후에 정렬했다.

풀이

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

int N,C,temp;
unordered_map<int,int> m,order;

bool cmp(pair<int,int> a, pair<int,int> b){
    if(a.second == b.second) return order[a.first] < order[b.first];
    else return a.second > b.second;
}

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

    cin >> N >> C;
    for(int i=0; i<N; i++){
        int num; cin >> num;
        if(m.find(num) == m.end()){
            temp++;
            order[num] = temp;
        }
        m[num]++;
    }
    vector<pair<int,int>> v(m.begin(),m.end());
    sort(v.begin(), v.end(), cmp);
    for(auto e : v){
        for(int i=0; i<e.second; i++){
            cout << e.first << " ";
        }
    }
    
    return 0;
}

코멘트

map을 value기준으로 정렬하려면 vector에 담은 후 커스텀정렬하자.