백준 [1713번] 후보 추천하기 문제 풀이
월드초등학교 학생회장 후보는 일정 기간 동안 전체 학생의 추천에 의하여 정해진 수만큼 선정된다. 그래서 학교 홈페이지에 추천받은 학생의 사진을 게시할 수 있는 사진틀을 후보의 수만큼 만들었다. 추천받은 학생의 사진을 사진틀에 게시하고 추천받은 횟수를 표시하는 규칙은 다음과 같다.
- 학생들이 추천을 시작하기 전에 모든 사진틀은 비어있다.
- 어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다.
- 비어있는 사진틀이 없는 경우에는 현재까지 추천 받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 자리에 새롭게 추천받은 학생의 사진을 게시한다. 이때, 현재까지 추천 받은 횟수가 가장 적은 학생이 두 명 이상일 경우에는 그러한 학생들 중 게시된 지 가장 오래된 사진을 삭제한다.
- 현재 사진이 게시된 학생이 다른 학생의 추천을 받은 경우에는 추천받은 횟수만 증가시킨다.
- 사진틀에 게시된 사진이 삭제되는 경우에는 해당 학생이 추천받은 횟수는 0으로 바뀐다.
후보의 수 즉, 사진틀의 개수와 전체 학생의 추천 결과가 추천받은 순서대로 주어졌을 때, 최종 후보가 누구인지 결정하는 프로그램을 작성하시오.
간단한 구현이구만(간단하게 하려다 너무 복잡하게 풀어서 시간이 꽤 걸렸다.)
- 추천 수(
recommand
)와 언제 추천을 받아서 들어왔는지(when
) 정보를 저장하는 배열을 두 개 만들었다.
#include <iostream>
#include <vector>
#define MAX_N 100
using namespace std;
int N;
int albumSize;
vector<int> card;
int recommand[MAX_N+1];
int when[MAX_N+1];
void getInput(){
cin >> N;
int stu; cin >> stu;
for(int i=0; i<stu; ++i){
int temp; cin >> temp;
card.push_back(temp);
}
}
// 학생 번호와 인덱스를 받아옴
void putCard(int stuNum, int index){
// 추천 목록에 있다면 추천수 하나 늘림
if(recommand[stuNum]){
++recommand[stuNum];
return;
}
// 사진 틀이 비어있다면 사진틀에 하나 추가시킴
// 앨범 크기 하나 늘림
if(albumSize < N){
++recommand[stuNum];
++albumSize;
when[stuNum] = index;
return;
}
// 사진 틀이 꽉차있고 새로 넣어야 하는 경우
int minRec = 987654321;
int outNum = 0;
for(int stuIter=1; stuIter<=MAX_N; ++stuIter){
if(recommand[stuIter] == 0){
continue;
}
// 가장 적은 추천수를 찾음
if(minRec > recommand[stuIter]){
minRec = recommand[stuIter];
outNum = stuIter;
continue;
}
// 추천수가 같다면 가장 먼저 들어온 애를 뺀다.
if(minRec == recommand[stuIter]){
if(when[stuIter] < when[outNum]){
outNum = stuIter;
}
}
}
// 빼야 하는 아이
recommand[outNum] = 0;
when[outNum] = 987654321;
// 새로 넣는 아이
recommand[stuNum] = 1;
when[stuNum] = index;
}
void solve(){
getInput();
for(int i=1; i<=card.size(); ++i){
putCard(card[i-1], i);
}
for(int i=1; i<=MAX_N; ++i){
if(recommand[i]){
cout << i << " ";
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}
- 자만하지 말자