백준 1713번: 후보 추천하기

문제링크 :https://www.acmicpc.net/problem/1713

1713번: 후보 추천하기

 문제설명 

 

1.  학생회장 선거를 하는데 후보를 등록하면 사진을 걸 수있는 사진틀이 제한되어있다.

2.  사진틀이 비어있다면 후보사진을 게시하고 사진틀이 꽉차있다면 추천수가 가장 낮은것중 가장 먼저 게시된 사진을        뺴고 새로운 후보의 사진을 등록한다.

3. 마지막에 사진이 게시되어있는 후보의 번호를 출력하시오.

 

 알고리즘 

 

1. 사진틀이 비어있다.

   - 후보의 사진이 게시되어있다 ( 추천수 +1)

   - 후보의 사진이 게시되어있지않다. (게시)

 

2. 사진틀이 비어있지 않다.

   - 후보의 사진이 게시되어있다 (추천수 +1)

   - 후보의 사진이 게시되어 있지 않다. -> 게시 되어있는 후보중 최소추천수를 받은 후보의 사진을 떼고 현재

     후보의 사진을 건다.

 

 

 코드 

 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int recommend[101];
 
int main() {
 
    cin.tie(NULL);
    ios::sync_with_stdio(0);
 
    int N, M;
    cin >> N >> M;
 
    //순서 , 사진
    vector<pair<int, int>> v(N);
 
 
    for (int i = 0; i < M; i++) {
        int num;
        cin >> num;
        recommend[num]++;
 
        bool change = true;
        for (int j = 0; j < N; j++) {
 
            //사진틀이 비어있는 경우
 
            if (v[j].second == 0) {
                v[j].second = num;
                v[j].first = i;
                change = false;
                break;
            }
 
            //이미 후보자의 사진이 등록되 있는 경우
 
            else if (v[j].second == num) {
                change = false;
                break;
            }
 
        }
 
        //사진틀이 비어있지않고 사진틀에 후보자의 사진이 없을경우
 
        if (change) {
 
            int idx = 0;
 
            for (int j = 1; j < N; j++) {
 
                //제일 추천 수가 낮은 사진들이 여러개인 경우
                if (recommend[v[j].second] == recommend[v[idx].second]) {
 
                    //먼저 등록된 
                    if (v[j].first < v[idx].first) idx = j;
 
                }
 
                //추천수가 낮은 순서로
                else if (recommend[v[j].second] < recommend[v[idx].second]) {
                    idx = j;
                }
            }
 
            recommend[v[idx].second] = 0; //바꿔쳐지면 추천수 초기화
 
            v[idx].first = i;
            v[idx].second = num;
 
        }
    }
 
    vector<int> picture;
 
    for (int i = 0; i < N; i++) {
        picture.push_back(v[i].second);
    }
 
    sort(picture.begin(), picture.end());
    for (int i = 0; i < N; i++)cout << picture[i] << " ";
}