백준 1713번 - 후보 추천하기

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

시뮬레이션 문제로, 문제에 제시된대로 구현하면 된다.

조금 까다로웠던 점은 사진틀이 비어있지 않을 때, 

추천 회수가 적은 순으로하고 동일하면 이전에 추천 받은거를 빼줘야 하는 것이다.

우선 배열에 값을 저장하고 배열이 꽉 차 있으면 현재 추천받은 학생이 이전에 추천받은 적이 있는지, 

만약 없다면 배열의 모든 값을 우선순위 큐에 집어넣은 다음에

가장 상위에 있는(추천 회수가 적고 이전에 추천받은) 번호를 빼준 다음에 배열에 값을 수정해줄수 있도록 했다.

deque로 문제를 풀 수 있을 거 같은데 아직 자료구조를 능숙하게 다루지 못하는거 같아서

다른 방식으로 문제를 해결하면 바로 업로드를 할 생각이다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
 
struct str {
    int num;
    int vote;
    int times;
    str(int num, int vote, int times) :num(num), vote(vote), times(times) {};
};
 
bool operator<(str s1, str s2) {
    //투표 적은 순, 동일하면 먼저 들어온 순으로
    if (s1.vote == s2.vote)
        return s1.times > s2.times;
    else
        return s1.vote > s2.vote;
}
int main() {
 
    std::ios_base::sync_with_stdio(false);
 
    int photo_size;
    int T=0;
    cin >> photo_size >> T;
 
    int recommend_num=0;
    vector<int> exists(101, 0); //추천 유무
    vector<str> vec;
 
    for (int  testCase= 1; testCase <= T; testCase++) {
        cin >> recommend_num;
 
        //해당 후보 이전에 추천 받았을 때
        if (exists[recommend_num]) {
 
            for (int i = 0; i < vec.size(); i++) {
                if (vec[i].num == recommend_num) {
                    vec[i].vote += 1; //투표수 증가
                    break;
                }
            }
            continue;
        }
        
        exists[recommend_num]++;
        if ((int)vec.size() < photo_size) { //아직 사진틀 여유 있으면
            vec.push_back(str(recommend_num, 1, testCase));
            continue;
        }
        
 
        priority_queue<str> pq;
        for (int i = 0; i < vec.size(); i++) {
            pq.push(vec[i]);
        }
 
        str s = pq.top();
        for (int i = 0; i < vec.size(); i++) {
            if (vec[i].num == s.num) {
                exists[s.num] = 0;
                vec[i].num = recommend_num;
                vec[i].vote = 1;
                vec[i].times = testCase;
                break;
            }
        }
    }
 
    vector<int> ans;
    for (int i = 0; i < vec.size(); i++) {
        ans.push_back(vec[i].num);
    }
 
    sort(ans.begin(), ans.end());
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << " ";
 
    return 0;
}