[ 백준 / C++ ] 2910 : 빈도 정렬

[ 문제 ]

 

2910번: 빈도 정렬

 

[ 접근방법 ]

 

각 수의 등장 횟수를 num에 저장하고,

각 수가 처음 등장한 순서를 fidx에 저장한다.

 

map 자료구조에 저장하여 삽입 및 조회를 O(log n) 만에 할 수 있다.

map 내부에서의 정렬은 필요가 없기 때문에 unordered_map을 사용하면 O(1) 도 가능하다.

 

map에 저장한 정보를 토대로 빈도 정렬을 하도록 cmp 함수를 정의하면 끝이다.

 

[ 소스코드 ]

 

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

int n, c;
map<int, int> num, fidx;
vector<int> vec;

bool cmp(int x, int y)
{
    if (num[x] != num[y])
        return num[x] > num[y];
    return fidx[x] < fidx[y];
}

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

    cin >> n >> c;
    for (int i = 0; i < n; i++)
    {
        int cnt;
        cin >> cnt;

        num[cnt]++;

        if (!fidx.count(cnt))
        {
            fidx[cnt] = i;
        }

        vec.push_back(cnt);
    }

    sort(vec.begin(), vec.end(), cmp);

    for (auto i : vec)
        cout << i << " ";

    return 0;
}