[백준] 1713 - 후보 추천하기 (C++)

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

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

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

사진틀의 개수와 전체 학생의 추천 결과가 순서대로 주어질 때, 최종 후보를 오름차순으로 출력하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 1 ≤ N ≤ 20
• 1 ≤  전체 학생의 총 추천 횟수 ≤ 1,000
• 1 ≤ 학생 번호 ≤ 100

 

사진을 대체할 때 추천 수와 게시된 시간을 기준으로 정렬해야 할 것 같아서 vector나 priority_queue, map으로 시도해봤지만 로직이 너무 복잡하고 정렬하기 어려워서 간단하게 int 배열만 사용해서 구현했다.

 

추천 받은 학생 번호가 사진틀에 존재한다면 추천 수만 증가시키면 된다. 존재하지 않는다면 사진틀에 빈 자리가 있는지 확인해야 한다. 빈 자리가 있다면 사진틀에 해당 학생의 사진을 넣는다. 빈 자리가 없다면 사진을 대체해야 하므로 조건에 맞는, 제거할 사진틀의 번호를 얻어 사진틀에서 제거한 뒤, 새로운 사진을 넣는다.

 

사진을 제거할 때 관련 정보를 모두 초기화해야 하고, 대체할 학생 번호를 구할 때 사진틀에 있는 학생 번호 중 추천 받은 수가 제일 적고 가장 오래 전에 게시된 사진의 학생 번호를 구하는 걸 고려해서 풀어야 한다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. N, 전체 학생의 총 추천 횟수 M 입력받기
2. M만큼 반복문을 돌리면서 추천 받은 학생 번호 입력받기
   1. 사진틀에 해당 학생 번호가 있는지 확인
      1. 있으면 추천 수 증가시키기
      2. 없으면 사진틀에 빈 공간이 있는지 확인
         1. 있으면 사진틀에 사진 넣기
         2. 없으면 사진틀에 있는 것들 중 추천 수가 가장 작고 가장 오래 전에 게시된 사진을 제거하고, 해당 학생의 사진을 추가하기
3. 사진틀에 있는 학생 번호를 오름차순으로 출력

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

pass

 

---

정답 코드

#include <iostream>
#include <algorithm>
#define pii pair<int,int>
using namespace std;

int n,m,x,cnt,score[101],post[101];
bool frame[101];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(); cout.tie();

    cin >> n >> m;
    for (int i=1; i<=m; i++) {
        cin >> x;

        if (frame[x]==0) { // 사진틀에 없음
            if (cnt<n) { // 사진틀에 넣기
                frame[x] = 1;
                post[x] = i;
                score[x]++;
                cnt++;
            }
            else { // 사진 대체
                int mn_rec=1001,mn_time=22,rep=0;
                for (int i=1; i<101; i++) {
                    if (frame[i]==1 && mn_rec > score[i]) {
                        mn_rec = score[i];
                        mn_time = post[i];
                        rep = i;
                    }
                    else if (frame[i]==1 && mn_rec == score[i]) {
                        if (post[i] > 0 && mn_time > post[i]) {
                            mn_time = post[i];
                            rep = i;
                        }
                    }
                }

                frame[rep] = 0;
                post[rep] = 0;
                score[rep] = 0;
                
                frame[x] = 1;
                post[x] = i;
                score[x]++;
            }
        }
        else { // 사진틀에 있음
            score[x]++;
        }
    }

    for (int i=1; i<101; i++) {
        if (frame[i]==1) cout << i << ' ';
    }
}