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

문제

바로가기

월드초등학교 학생회장 후보는 일정 기간 동안 전체 학생의 추천에 의하여 정해진 수만큼 선정된다.

그래서 학교 홈페이지에 추천받은 학생의 사진을 게시할 수 있는 사진틀을 후보의 수만큼 만들었다.

추천받은 학생의 사진을 사진틀에 게시하고 추천받은 횟수를 표시하는 규칙은 다음과 같다.

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

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

 

 

입력

첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20)

둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대로 주어진다.

총 추천 횟수는 1,000번 이하이며 학생을 나타내는 번호는 1부터 100까지의 자연수이다.

 

 

출력

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

 

 

해결 방법

현재 게시판에 게시된 후보들의 정보를 벡터에 넣고 탐색하면 된다.

이때 고려해야 할 사항은 크게 3가지이다.

1️⃣ 추천받은 학생의 번호
2️⃣ 특정 학생이 추천받은 횟수
3️⃣ 추천받은 시기

1, 2는 벡터의 구조를 아래와 같이 선언함으로써 저장할 수 있다.

vector <pair<학생번호, 추천받은 수>>

 

그럼 3번, 즉 추천받은 시기는 어떻게 파악해야될까?

필자는 추천받은 시기도 벡터에 같이 넣으려했지만, 그럴 필요없이 먼저 게시된 학생이 앞쪽에 배치되도록 벡터를 정렬해주면 된다.

이렇게 해도 되는 이유는 우리가 최종적으로 출력할 답이 게시판에 게시된 학생 순서를 그대로 출력하는게 아니라,
학생 번호를 오름차순으로 출력하는 것이기 때문에 현재 게시판에 누가 남아있느냐만 중요하기 떄문이다.

 

예를 들어, 게시판의 크기는 3이고 추천받은 학생 목록이 [1, 1, 2, 2, 2, 3, 3, 4, 4, 5] 라고 해보자.

[1, 1, 2, 2, 2, 3, 3] 경우를 모두 처리하고 나면 현재 게시판에 저장된 학생은 [1, 2, 3]번이고 각각 추천받은 횟수는 [2, 3, 2]번이다.

다음으로 4번 학생을 게시해야 하는데 게시판이 다 찼기 때문에 추천받은 수가 가장 적은 학생을 제거해야 한다.

1번과 3번 학생이 2번씩 추천을 받았기 때문에 둘 중 하나를 제거해야 되는데,1번이 더 앞에 있고 그 말은 1번이 먼저 추천을 받았단 뜻이기 때문에 1번을 제거하면 된다.

 

문제에서는 제거한 학생 자리에 추가할 학생 사진을 게시하라고 되어있는데, 이 부분 때문에 풀이가 좀 오래걸렸다.

우리는 위에서 먼저 게시된 학생이 앞쪽에 배치되도록 벡터를 정렬되게끔 한다고 했기 떄문에

1번 학생 자리에 4번을 삽입하는게 아니라 게시판의 제일 뒤에 4번 학생을 삽입해야 한다.

그럼 게시판에 게시된 후보는 [2, 3, 4]이고 각각 추천받은 횟수는 [3, 2, 1] 이다.

다음으로 또 4번 학생이 들어와야 하므로 게시판의 상태는 [2, 3, 4]로 변함없고 추천받은 횟수만 각각 [3, 2, 2]로 변경된다.

다음으로는 5번 학생이 들어와야 하는데 현재 추천 횟수가 가장 적은 학생은 3번과 4번이고

이 중 3번이 더 앞에 있으므로(먼저 추천 받았으므로) 3번을 제거하고 5번을 추가하면 된다.

최종적으로 게시판에 게시된 후보는 [2, 4, 5]이고 이를 오름차순 정렬한 후 정답을 출력하면 된다.

 

 

내 코드

// [1713] 후보 추천하기
// 구현, 시뮬레이션
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, k;
vector <pair<int, int> > photo; // <학생번호, 추천 수>

void removePhoto()
{
	int minRecommend = photo[0].second;
   
    for(int i = 0; i < photo.size(); i++) {
		minRecommend = min(minRecommend, photo[i].second);
	}

	for(int i = 0; i < photo.size(); i++){
		if (minRecommend == photo[i].second) {
			photo.erase(photo.begin() + i); 
			break;
		}
	}
}

void solution(int student)
{
    bool flag = false;
    for(int i = 0; i < photo.size(); i++) { 
        if(student == photo[i].first) { // 이미 추천된 후보
            flag = true; 
            photo[i].second++; 
            return;
        }
    }

    if(flag == false) { // 새로운 후보
        if(photo.size() <= n) {
            if(photo.size() == n) { // 빈 사진틀 없는 경우
                removePhoto(); 
            }
            photo.push_back(make_pair(student, 1));
        }
    }
}

void input()
{
    int student;
    cin >> n;
	cin >> k;
    for(int i = 0; i < k; i++) {
		cin >> student;
        solution(student);
    }
}

void output()
{
    sort(photo.begin(), photo.end());
    for(int i = 0; i < photo.size(); i++) {
		cout << photo[i].first << " ";
	}
}

int main()
{
    input();
    output();
	return 0;
}