[백준 1713] - 후보 추천하기 C++

문제

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

1713번: 후보 추천하기

접근방법

deque를 이용하면, index로 값을 찾을 수 있다.

값의 범위가 크지 않아서 돌릴 때마다 deque에서 값이 있나 찾아보고 없으면 넣고, 있으면 rec++해줬다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <deque>

using namespace std;

#define FOR(i, n) for(int i=0;i<n;i++) 

struct node {
    int sno, rec, order;

    bool operator<(const auto& other) const {
        return (rec != other.rec) ? rec < other.rec : order < other.order;
    }
};

int n, m;
deque<node> dq;
int main() {
    cin >> n >> m;
    vector<int> answer;
    FOR(i, m) {
        int sno;
        cin >> sno;
        bool flag = false;
        FOR(j, dq.size()) if (dq[j].sno == sno) {
            dq[j].rec++;
            flag = true;
        }
        if (!flag) {
            if (dq.size() < n) dq.push_back({sno, 1, i});
            else {
                dq.pop_front();
                dq.push_back({sno, 1, i});
            }
        }
        sort(dq.begin(), dq.end());
    }

    FOR(i, dq.size()) answer.push_back(dq[i].sno);
    sort(answer.begin(), answer.end());
    FOR(i, answer.size()) cout << answer[i] << " ";

    return 0;
}

개선할 점

구현은 테스트케이스 생각하는 게 일이다.

 

다양한 테스트케이스를 시도해보자.