[BOJ] C++ 2910: 빈도 정렬 - 정렬 기준 만들어서 정렬하기

2910번: 빈도 정렬

9 3
1 3 3 3 2 2 2 1 1

ans : 1 1 1 3 3 3 2 2 2

---

빈도를 기준으로 정렬하되, 들어온 순서를 유지하면서 정렬해야 한다. 빈도만 기준이었다면 떠오르는 방법은 아래와 같다.

1. 맵에 빈도를 key로 값을 value로 해서 삽입한다.
2. pair vector에 빈도, 값으로 삽입을 한 뒤 빈도를 기준으로 sort를 한다.

두 방법에서 기존 입력의 순서를 유지할 방법을 생각해 봤는데, sort를 병합 정렬로 직접 구현하지 않는 이상 맵이나 벡터를 확장하는 방법이었다.

1. 맵 2개 사용, 하나는 key로 빈도를 하나는 key로 입력된 순서를 저장해서 비교 함수를 잘 구현한다.
2. 3차원 벡터로 구현, 차례대로 order, count, value 저장

이 중 2번 방법을 선택해서 구현했다.

/** 정렬 2910 빈도 정렬 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int n, c;

bool cmp(const pair<int, pair<int, int>> &a, const pair<int, pair<int, int>> &b)
{
    if (a.second.first != b.second.first)
        return a.second.first > b.second.first;
    return a.first < b.first;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> c;
    vector<pair<int, pair<int, int>>> num; // order, cnt, value 순으로 저장
    for (int i = 0; i < n; i++)
    {
        int val;
        cin >> val;
        int k;
        for (k = 0; k < num.size(); k++)
            // num안에 val이 있다면 cnt만 증가
            if (num[k].second.second == val)
            {
                num[k].second.first++;
                break;
            }

        if (k == num.size())
            // 못 찾았으므로 num에 삽입, 순서는 i번째 삽입이다.
            num.push_back({i, {1, val}});
    }
    // num을 cnt 기준으로 내림차순 정렬하면 되는데, cnt가 같으면 order 기준 오름차순 정렬
    sort(num.begin(), num.end(), cmp);
    // 정렬 완료, 차례대로 cnt만큼 val을 출력하면 된다.
    for (auto x : num)
        while (x.second.first--)
            cout << x.second.second << ' ';
}

문제를 다 풀고 안 사실인데, 간단하게 stabe_sort를 활용하면 됐었다. 내가 구현한 것과 정확히 똑같은 동작을 하는 stl이 이미 있었다.