1713: 후보 추천하기

• toc {:toc}

문제 확인하기

1713: 후보 추천하기 문제 확인하기

풀이

이 문제에서 풀어야 할 지점은 3번이다.

3. 비어있는 사진틀이 없는 경우에는 현재까지 추천 받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 자리에 새롭게 추천받은 학생의 사진을 게시한다. 이때, 현재까지 추천 받은 횟수가 가장 적은 학생이 두 명 이상일 경우에는 그러한 학생들 중 게시된 지 가장 오래된 사진을 삭제한다.

• 비어있는 사진틀이 없는 경우 추천 수가 가장 적은 학생을 찾는 알고리즘
• 추천 수가 동일할 경우 가장 오래된 학생 선택

recommend 배열은 추천 횟수를 세는 배열, check 배열에서 학생이 사진틀에 뽑힌 경우를 확인할 뿐만 아니라 old를 사용해서 오래된 순서를 나타낸다.

이 부분 구현이 되었다면 나머지 부분은 문제 그대로 풀이하면 된다.

다만, 사진틀에 있는 학생이 추천받았을 때 old는 갱신되지 않는다.

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
 
int recommend[105];     // 추천 횟수
int check[105];         // 사진틀에 들어왔는지 여부 체크
vector<int> frame;
 
int main(){
    ios::sync_with_stdio(true);
    cin.tie(0); cout.tie(0);
 
    int N, size, num, old = 0;
    check[104] = 99999;
 
    cin >> N;
    
    size = N;
 
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> num;
        old++;
 
        // Frame이 채워져 있는 상태에서 새로운 후보가 들어온 경우
        if (frame.size() == size && !check[num-1]){
            int idx = -1;
            pair<int, int> min = {104, 99999};
            for (int k=0; k<frame.size(); k++){
                int n = frame[k];
                // 현재까지 추천수가 가장 적은 학생 추출
                if (min.Y > recommend[n-1]) {
                    idx = k;
                    min.X = n;
                    min.Y = recommend[n-1];
                }
                // 추천수가 동일할 때 오래된 학생 추출
                else if (min.Y == recommend[n-1]){
                    if (check[min.X-1] > check[n-1]){
                        idx = k;
                        min.X = n;
                        min.Y = recommend[n-1];
                    } 
                }
            }
            recommend[min.X-1] = 0;
            check[min.X-1] = 0;
 
            frame[idx] = num;
            recommend[num-1]++;
            check[num-1] = old;
        }
        // 사진틀에 있는 후보가 추천을 받은 경우
        else if (check[num-1]){
            recommend[num-1]++;
        }
        else{
            recommend[num-1]++;
            check[num-1] = old;
            frame.push_back(num);
        }
    }
 
    sort(frame.begin(), frame.end());
 
    for (int i : frame){
        cout << i << " ";
    }
 
    return 0;
}