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

백준 1713 후보 추천하기 문제
백준 1713 후보 추천하기 소스코드

📄 문제 설명

Problem

학생회장 후보는 일정 기간 동안 전체 학생의 <추천>에 의해 <정해진 수>만큼 선정된다.
학교 홈페이지에는 추천받은 학생의 사진을 게시할 수 있는 사진틀을 <후보의 수>만큼 만들었다.

추천받은 학생의 사진을 사진틀에 게시하고 추천받은 횟수를 표시하는 <규칙>은 다음과 같다.
ⓐ 학생들이 추천을 시작하기 전에 <모든 사진틀은 비어있다>.
ⓑ 어떤 학생이 특정 학생을 추천하면, <추천받은 학생의 사진이 반드시 사진틀에 게시>되어야 한다.
ⓒ <비어있는 사진틀이 없는 경우>
  ① 현재까지 <추천 받은 횟수가 가장 적은 학생의 사진을 삭제>
  ② 그 자리에 새롭게 <추천받은 학생의 사진을 게시>한다.
ⓓ 현재까지 추천 받은 횟수가 가장 적은 학생이 <두 명 이상>일 경우,
  ① 그러한 학생들 중 게시된 지 <가장 오래된 사진을 삭제>한다.
ⓔ 현재 사진이 게시된 학생이 다른 학생의 추천을 받은 경우
  ① <추천받은 횟수만 증가>시킨다.
ⓕ 사진틀에 <게시된 사진이 삭제>되는 경우
  ① 해당 학생이 <추천받은 횟수는 0>으로 바뀐다.

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

Input

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

Output

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

Example Input

3
9
2 1 4 3 5 6 2 7 2

Example Output

2 6 7

📝 문제 해설

후보 중 사진 틀(photo)에 게시될 수 있는 인원은 총 N명이다.
총 M번의 투표 중에서 위의 규칙을 따라 게시될 N명을 선출해 오름차순으로 정렬하는 프로그램이다.

⚠ 여기서 가장 중요한 부분은 위와 같이 photo가 가득 차 있을 때,
<삭제할 학생을 선택>하는 방법이다.

▶ 표준 라이브러리의 sort() 함수 사용 Sort C++ Reference

#include <algorithm>

// default : 오름차순 정렬
template <class RandomAccessIterator>
  void std::sort (RandomAccessIterator first, RandomAccessIterator last);

// custom : 정렬 조건이 여러개일 때 comp 함수를 만들어 정렬 기준 재정의
template <class RandomAccessIterator, class Compare>
  void std::sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Compare() 함수

Compare() 함수로 정렬 기준을 재정의하여 사용
Compare() 함수는 2개의 데이터의 위치에 대하여 Swap여부를 결정하는 함수.
Compare() 함수의 인자 중 앞에 있는 데이터가 위치적으로 앞쪽에 있는 데이터

C++의 경우,

bool comp(const int o1, const int o2){
    return true; // 두 데이터를 바꾸지 않는다.
    return false; // 두 데이터 o1과 o2을 바꾼다. (Swap)
}

// 오름차순 comp()
bool comp(const int o1, const int o2){
    return o1 <= o2;
}

// 내림차순 comp()
bool comp(const int o1, const int o2){
    return o1 > o2;
} 

문제로 돌아와서,

위에 설명된 sort() 메소드의 Compare() 함수에 정렬 기준을 재정의하여 문제를 해결하자.

삭제 될 후보의 조건은 아래와 같다.
<추천 받은 횟수가 가장 적은>
<가장 오래된 사진>

추천수를 나타내는 배열 rcm[]와 사진틀에 게시되어 있던 시간을 나타내는 배열 dur[]을 선언하고,
추천수와 게시기간 조건에 따라 Compare()함수를 재정의 해주었다.

1) 추천받은 횟수 rcm[o1] == rcm[o2]가 같다면,
   1-1) 게시된 기간 dur[o1] dur[o2]를 비교해 더 오래된 사진이 뒤로가게 한다.
2) rcm[o1] > rcm[o2] 라면 o1과 o2의 자리를 바꿀 필요가 없고, (return true)
3) rcm[o1] < rcm[o2] 라면 o1과 o2를 swap 해주어야 한다. (return false)

※ 아래 소스코드 comp() 참고

</> Source Code

#include <bits/stdc++.h>

using namespace std;

int rcm[110] = {0, }; // 추천수 배열
int dur[110] = {0, }; // 게시 기간 배열
	
bool comp(const int o1, const int o2){
	if(rcm[o1] == rcm[o2]){
		if(dur[o1] < dur[o2]){
			return true;
		}
		else{
			return false;
		}
	}
	else if(rcm[o1] > rcm[o2]){
		return true;
	}
	else{
		return false;
	}
}

int main() {
	int n, c;
	vector<int> photo; // 사진틀
	
	scanf("%d %d", &n, &c);
	
	for(int i = 0; i < c; i++){
		int x;
		scanf("%d ", &x); // 후보 입력
		
		rcm[x]++;
		
		for(int j = 0; j < photo.size(); j++){
			dur[photo[j]]++; // 후보 입력마다 사진틀에 게시된 후보 기간 증가
		}
		
		bool exist = false;
		
		for(int j = 0; j < photo.size(); j++){
			if(photo[j] == x){
				exist = true;
				break;
			}
		}
		
		if(!exist){
			if(photo.size() < n){
				photo.push_back(x);
			}else{
				sort(photo.begin(), photo.end(), comp);
                		// 재정의한 정렬 기준에 따라 사진틀 정렬
				rcm[photo.back()] = 0;
				dur[photo.back()] = 0;
				photo.back() = x;
			}
		}
		
	}
	
	sort(photo.begin(), photo.end()); // 후보 오름차순 정렬
	
	for(int i = 0; i < photo.size(); i++){
		printf("%d ", photo[i]);
	}
	
}