(C++) 백준 2910번 - 빈도 정렬

 

문제 링크 : https://www.acmicpc.net/problem/2910

2910번: 빈도 정렬

문제 풀이

stable_sort와 커스텀 비교 함수를 사용하여 풀이하였다.

pair를 사용해 값과 빈도수를 동시에 저장하는 것과 stable_sort를 사용하는 것이 중요하다고 할 수 있다.

#include <iostream>
#include <algorithm>
#include <vector>
#define X first
#define Y second

using namespace std;

int n, c;
vector<pair<int, int> > v; // 첫번째 int는 값, 두번째 int는 나타난 빈도수


bool cmp(const pair<int, int> &p1, const pair<int, int> &p2){ // stable_sort에서는 무조건 const가 필요
    return p1.Y > p2.Y;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> c;

    for(int i = 0; i < n; ++i){
        bool isprs = false; // 이미 존재하는지
        int tmp;
        cin >> tmp;
        for(auto& k : v){ // 값을 수정
            if(k.X == tmp){ // 이미 존재한다면
                k.Y++; // 빈도수 증가
                isprs = true;
                break;
            } 
        }
        if(!isprs) v.push_back({tmp, 1}); // 존재하지 않으면 vector에 저장
    }
    stable_sort(v.begin(), v.end(), cmp); // 같은 우선 순위에서는 순서 유지를 위해 stable_sort 사용
    for(auto k : v){
        for(int i = 0; i < k.Y; i++) cout << k.X << " ";
    }
}