백준 1713번 후보 추천하기 (C++)

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

1713번: 후보 추천하기

 

 이 문제에서 기억해둬야할 점은 다음과 같다. 

 

1. n은 앨범의 순서, m은 추천을 받는 횟수이다. 학생의 번호는 1번 ~ 100번까지 존재한다.

2. 문제에서 언급한 사항들을 반드시 모두 지켜야한다. 

2번과 5번을 간과하기 쉽다.

---

이 문제를 풀기 위해 필요한 변수와 로직은 다음과 같이 구현했다.

로직만 이해한다면 코드를 하나하나 설명하지 않아도 되므로, 구체적인 설명은 생략한다.

 

[변수]

구조체 frame = 학생번호, 앨범 순서, 학생 점수

student [101] = 해당 번호 학생의 추천수를 뜻함

• 학생의 번호는 1~100까지 고정적으로 주어진다.

 

[알고리즘]

사진틀의 길이가 n보다 작다.

(1) 자신의 것이 있다면 점수만 업데이트하기

(2) 자신의 것이 없다면 벡터의 맨 뒤에 추가

 

사진틀의 길이가 n이상 이다.

(1) 자신이 것이 있으면 점수만 업데이트하기

(2) 자신의 것이 없다면

      (2-1) 가장 작은 추천을 받은 학생(=frame[0])의 점수를 0으로 초기화

      (2-2) 그 자리를 대체해서 들어간다.

 

[정렬] 

comp1 = 추천수가 작은 순이 앞으로 옴.

추천수가 동일하면 사진틀에 더 오래전에 들어온 학생이 앞으로 옴.

• 이 정렬은 학생이 한 번 들어올때마다 사용해준다.

comp2 = 학생 번호가 작은 순으로 앞으로 옴 (정답을 출력할때 쓰임)

---

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct frame{
    int number;
    int order;
    int score;
};

bool comp1(const frame &a, const frame &b){
    if(a.score==b.score) return a.order<b.order;
    else return a.score<b.score;
}

bool comp2(const frame &a, const frame &b){
    return a.number < b.number;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n,m,s,o=1;
    cin >> n >> m;
    vector<frame> f;
    int student[101];
    for(int i=0; i<101; i++) student[i] = 0;
    for(int i=0; i<m; i++){
        cin >> s;
        student[s]++;
        if(f.size()<n){
            if(student[s]==1) f.push_back({s,o,1});
            else{
                for(int i=0; i<f.size(); i++){
                    if(f[i].number==s){
                        f[i].score++;
                        break;
                    }
                }
            }
        }
        else{
            if(student[s]==1){
                student[f[0].number] = 0;
                f[0] = {s,o,1};
            }
            else{
                for(int i=0; i<f.size(); i++){
                    if(f[i].number==s){
                        f[i].score++;
                        break;
                    }
                }
            }
        }
        o++;
        sort(f.begin(),f.end(),comp1);
    }
    sort(f.begin(),f.end(),comp2);
    for(int i=0; i<f.size(); i++) cout << f[i].number << " ";
    cout << "\n";
    return 0;
}