[백준 2910번] [Map] 빈도 정렬

Approach

일단, 빈도 순으로 정렬하는 것이므로 Map 자료 구조를 활용해서 몇 번 출현했는지를 체크해주면 된다.

독특한 지점은 등장하는 횟수가 같다면 먼저 나온 것이 앞에 있어야 한다는 점이다.

 

이 부분은 먼저 나오는 번호를 따로 저장해두면 된다. 개인적으로는 문제에서 C를 준 이유가 있다고 판단하여서 vector를 활용해 정렬하였다.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

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

int main(void){
    fastio;
    int n, c;
    cin >> n >> c;
    map<int, int> first_occurence;
    map<int, int> num_occur;

    for(int i = 0; i < n; i++){
        int n;
        cin >> n;
        if(first_occurence.find(n) == first_occurence.end()){
            first_occurence[n] = i;
        }
        num_occur[n] += 1;
    }

    vector<pair<pair<int, int>, int> > v;

    for(map<int, int>::iterator it = num_occur.begin(); it != num_occur.end(); it++){
        v.push_back(make_pair(make_pair(it -> second, first_occurence[it -> first]), it -> first));
    }

    sort(v.begin(), v.end(), compare);

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