백준 1713 후보 추천하기

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

1713번: 후보 추천하기

문제

월드초등학교 학생회장 후보는 일정 기간 동안 전체 학생의 추천에 의하여 정해진 수만큼 선정된다. 그래서 학교 홈페이지에 추천받은 학생의 사진을 게시할 수 있는 사진틀을 후보의 수만큼 만들었다. 추천받은 학생의 사진을 사진틀에 게시하고 추천받은 횟수를 표시하는 규칙은 다음과 같다.

1. 학생들이 추천을 시작하기 전에 모든 사진틀은 비어있다.
2. 어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다.
3. 비어있는 사진틀이 없는 경우에는 현재까지 추천 받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 자리에 새롭게 추천받은 학생의 사진을 게시한다. 이때, 현재까지 추천 받은 횟수가 가장 적은 학생이 두 명 이상일 경우에는 그러한 학생들 중 게시된 지 가장 오래된 사진을 삭제한다.
4. 현재 사진이 게시된 학생이 다른 학생의 추천을 받은 경우에는 추천받은 횟수만 증가시킨다.
5. 사진틀에 게시된 사진이 삭제되는 경우에는 해당 학생이 추천받은 횟수는 0으로 바뀐다.

후보의 수 즉, 사진틀의 개수와 전체 학생의 추천 결과가 추천받은 순서대로 주어졌을 때, 최종 후보가 누구인지 결정하는 프로그램을 작성하시오.

입력

첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대로 주어진다. 총 추천 횟수는 1,000번 이하이며 학생을 나타내는 번호는 1부터 100까지의 자연수이다.

출력

사진틀에 사진이 게재된 최종 후보의 학생 번호를 증가하는 순서대로 출력한다.

예제 입력 1 복사

3
9
2 1 4 3 5 6 2 7 2

예제 출력 1 복사

2 6 7

---

[풀이 과정]

1. 추천받은 학생들 정보를 input배열에 저장한다.

2. candidates 벡터 : 사진틀에 게시된 후보들을 저장한 벡터

- 현재 사진틀에 게시된 후보가 N보다 작을 때

1) 아직 게시되지 않은 후보이면 candidates 벡터에 추가하고 게시되었다는 표시로 number[input[i]]를 1로 바꿔준다.

2) 이미 게시된 후보이면 해당 후보를 찾아서 추천 횟수를 1증가시킨다.

 

- 현재 사진틀에 게시된 후보가 N 이상일 때

1) 아직 게시되지 않은 후보이면 sort함수를 통해 사진틀에서 제외될 후보를 찾고 그 자리를 현재 후보로 바꿔준다.

2) 이미 게시된 후보이면 해당 후보를 찾아서 추천 횟수를 1증가시킨다.

 

3. compare(INFO a, INFO b)

- 추천 횟수가 작은 순서대로 정렬하고 추천 횟수가 같은 경우엔 먼저 들어온 후보를 먼저 정렬한다.

 

4. 모든 과정이 끝나면 sort함수를 통해 사진틀에 있는 후보의 번호를 오름차순으로 출력한다.

 

어려운 문제는 아니었는데 처음에 MAX를 105로 해줘서 틀렸던 문제이다.

학생의 번호가 1~100이라는 조건만 보고 105로 설정했었는데 총 추천 횟수가 1000번 이하이기 때문에 input에 최대 1000개의 값이 들어간다. 따라서 MAX를 1000이 넘는 값으로 설정해야 했다.

 

---

[소스 코드]

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 1005;

int N, M, input[MAX], number[MAX];
struct INFO{
    int num, cnt, time;
};
vector <INFO> candidates;

bool compare(INFO a, INFO b){
    if(a.cnt < b.cnt) return true;
    else if(a.cnt == b.cnt){
        if(a.time < b.time) return true;
        else return false;
    }
    else return false;
}

bool compare2(INFO a, INFO b){
    if(a.num < b.num) return true;
    else return false;
}

int main(){
    scanf("%d %d", &N, &M);

    for(int i=0;i<M;i++) scanf("%d", &input[i]);

    for(int i=0;i<M;i++){
        if(candidates.size() < N) {
            if(number[input[i]] == 0){
                candidates.push_back({input[i], 1, i});
                number[input[i]] = 1;
            }
            else{
                for(int j=0;j<candidates.size();j++){
                    if(candidates[j].num == input[i]){
                        candidates[j].cnt++;
                        break;
                    }
                }
            }
        }
        else {
            if(number[input[i]] == 0){
                sort(candidates.begin(), candidates.end(), compare);
                number[candidates[0].num] = 0;
                candidates[0].num = input[i];
                candidates[0].cnt = 1;
                candidates[0].time = i;
                number[input[i]] = 1;
            }
            else{
                for(int j=0;j<candidates.size();j++){
                    if(candidates[j].num == input[i]){
                        candidates[j].cnt++;
                        break;
                    }
                }
            }
        }
    }

    sort(candidates.begin(), candidates.end(), compare2);
    for(int i=0;i<candidates.size();i++){
        printf("%d ", candidates[i].num);
    }
    return 0;
}