[BOJ 백준] 1713번 후보 추천하기

문제

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

1713번: 후보 추천하기

접근

이 문제는 시뮬레이션 문제로 제시하는 조건대로 구현해주면 된다. 이때 조건이 많다면 빠트리고 구현한 게 없는지 확인하는걸 잊지 말자.

우리는 사진틀이 꽉 찼을 때 득표수가 작은 학생부터 밀어낸다. 이때 가장 작은 득표수를 가진 학생이 두 명 이상이라면 그중 사진틀에 먼저 걸린 학생을 밀어내야 하므로 언제 사진틀에 걸렸는지 기억할 필요가 있다. 따라서 배열을 2차원으로 선언하여 학생의 득표수와 사진틀에 걸린 시간을 저장해주었다.

또 사진틀에 현재 추천받은 학생이 걸려있는지를 알기 위해 따로 배열을 만들어 사진틀에 걸려있는 여부를 체크해줬다.

추천을 다 받은 후엔 sort로 학생 번호에 따라 정렬하여 출력해줬다.

 

코드

// algorithm study
// BOJ_1713 후보 추천하기

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int chk[110][2] = {0};

bool v_sort(int a, int b) {
    if (chk[a][0] == chk[b][0])
        return chk[a][1] > chk[b][1];
    return chk[a][0] > chk[b][0];
}

int main() {
    int n, m, time = 0, f[110] = {0};
    cin >> n >> m;
    vector<int> v;
    for (int i = 0; i < m; i++) {
        int num;
        cin >> num;
        chk[num][0]++;
        if (f[num] == 0) {
            if (v.size() == n) {
                sort(v.begin(), v.end(), v_sort);
                f[v[v.size() - 1]] = 0;
                chk[v[v.size() - 1]][0] = 0;
                v.pop_back();
            }
            v.push_back(num);
            chk[num][1] = time;
            f[num] = 1;
        }
        time++;
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study