BOJ)2910 빈도 정렬

문제: icpc.me/2910

수열이 존재할 때 수열에서 가장 많이 등장하는 빈도로 정렬을 하는 문제이다.

이 때 빈도가 같은 수는 먼저 등장한 순서대로 정렬을 해야한다.

우리는 수가 최대 10억까지 들어올 수 있으므로 빈도를 저장하기 위해 키값에 따른 값을 저장할 수 있는 map 자료 구조를 사용할 수 있다.

두개의 맵을 선언하여 하나는 빈도수를 하나는 들어온 순서를 저장한 뒤 

벡터에 빈도수와 키값을 삽입 시켜준 뒤 조건에 맞게 정렬을 해준 뒤 출력해주면 된다.

#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
int n, c, x;
map<int, int> mp;
map<int, int> m;
vector<pair<int, int>> p;
bool cmp(pair<int, int> a, pair<int, int> b) {
    if (a.first == b.first) {
        return m[a.second] < m[b.second];
    }
    return a.first > b.first;
}
int main() {
    scanf("%d%d", &n, &c);
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        mp[x]++;
        if (!m[x])
            m[x] = i + 1;
    }
    for (auto i : mp) 
        p.emplace_back(i.second, i.first);
    sort(p.begin(), p.end(), cmp);
    for (auto i : p) {
        for (int j = 0; j < i.first; j++)
            printf("%d ", i.second);
    }
    return 0;
}