1713 - 후보 추천하기

문제

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

느낀점

구현 기본 문제, map은 정렬이 안된다. 차라리 vector와 pair로 만들어야한다. 그렇게하면 코드는 좀 복잡해져도 정렬 가능하다. map으로 괜히 정렬하려다가 시간만 날림.. 구현 문제를 더 풀어야겠다..

풀이

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

using namespace std;

#define pii pair<int, int>

int main()
{
    int N;
    cin >> N;
    int C;
    cin >> C;
    deque<pair<int, pii>> count;
    for (int i = 0; i < C; i++)
    {
        int temp;
        cin >> temp;
        bool exist = false;
        for (size_t j = 0; j < count.size(); j++)
        {
            auto &c = count[j];
            if (c.first == temp)
            {
                c.second.first++;
                exist = true;
                break;
            }
        }
        if (!exist)
        {
            if (count.size() >= N)
            {
                int p = count.front().first;
                count.pop_front();
                count.push_back(make_pair(temp, make_pair(1, i)));
            }
            else
            {
                count.push_back(make_pair(temp, make_pair(1, i)));
            }
        }

        sort(count.begin(), count.end(), [](const pair<int, pii> &a, const pair<int, pii> &b) {
            if (a.second.first == b.second.first)
            {
                return a.second.second < b.second.second;
            }
            return a.second.first < b.second.first;
        });
    }

    sort(count.begin(), count.end(),
         [](const pair<int, pii> &a, const pair<int, pii> &b) { return a.first < b.first; });

    for (size_t i = 0; i < count.size(); i++)
    {
        cout << count[i].first << " ";
    }

    return 0;
}