백준 2910. 빈도 정렬 (정렬)

https://www.acmicpc.net/problem/2910

2910번: 빈도 정렬

조건을 고려하여 정렬하는 문제이다. 

 

1. 특징

1) 조건에 맞춰서 정렬

 

2. 구현 포인트

1) {1, 3, 3, 3, 2, 2, 2, 1, 1} 에서 마지막에 있는 1 두개도, 앞쪽에 1 1 1로 출력되어야한다.

다시말해 해당 수가 최초로 나온 위치를 기억할 필요가 있다. 이를 _map1에서 관리해준다. 이전에 나온적이 없는 수이면 (map에서 나온적이 없으면) cnt 값을 얻어서 _map1에 저장해준다. 

나는 이 부분을 단순히 먼저 나오면 먼저 출력된다라고 생각해서, 뒤에 나온 1들은 앞에서 1을 출력할 때 출력되지 않았다. 다시한번 강조하면, **최초로 나온 수와 함께 묶어서 한번에 출력해야한다는 사실을 잊지말자.

 

3. 코드

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> _vec;
unordered_map<int, int> _map;
unordered_map<int, int> _map1;

bool comp(pair<int, int>& a, pair<int, int>& b)
{
    if(_map[a.first] != _map[b.first]) return _map[a.first] > _map[b.first];
    else return a.second < b.second;
}

int main(void)
{
    int n, c;
    cin >> n >> c;

    int x;
    int cnt = 0;
    for(int i = 0; i < n; i++)
    {
        cin >> x;
        _map[x]++;
        if(_map[x] == 1) _map1[x] = cnt++; 
        _vec.push_back(make_pair(x, _map1[x]));
    }


    sort(_vec.begin(), _vec.end(), comp);

    for(int i = 0; i < n; i++)
    {
        cout << _vec[i].first << '\n';
    }
    
}