[BOJ] 1713번_후보 추천하기_구현

[문제]

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

학생회장 후보를 정하려고 한다. 학생회장 후보는 전체 학생의 추천에 의하여 선정된다. 학교 홈페이지에는 추천받은 학생의 사진을 게시할 수 있는 사진틀을 학생회장 후보의 수만큼 만들었다. 추천 받은 학생은 사진을 사진틀에 게시하고 추천받은 횟수를 표기한다. 규칙은 다음과 같다.

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

사진틀의 개수(후보의 수)와 전체 학생의 추천 결과를 입력받고, 최종 후보가 누구인지 결정하는 문제이다.

[사용 알고리즘]

구현

[풀이 핵심]

• 후보는 학생 번호와 투표수를 저장해야되기 때문에 구조체를 이용하였다.
• 구현 문제이므로 1~5번 조건을 충족시키는 프로그램을 만들면 된다.

  1. 빈 구조체 벡터를 만든다.
  2. 어떤 상황이던 추천을 받은 학생은 벡터에 push해줘야한다.
  3. 비어있는 사진틀이 없는 경우 구조체벡터를 처음부터 끝까지 탐색하며 count의 최소값을 찾고 다시 벡터를 처음부터 끝가지 탐색하며 최소값이 가장 먼저 나올때(게시된 지 가장 오래됨) 그 원소를 erase함수로삭제시켜준다. 이후 입력 받은 회장후보를 push해준다.
  4. 이미 회장후보에 올라와 있는 학생이 또 추천을 받으면 count만 증가시켜준다.
  5. 사진틀에 게시된 사진이 삭제되는 경우에는 해당 학생이 추천받은 횟수는 0으로 바뀐다.라는 조건인데, 3번에서 회장후보에서 떨어지는 학생은 erase처리를 해주므로 신경안써도 되는 항목이다.

[코드]

//boj1713번_후보 추천하기_구현

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct student {
	int num;
	int count;
};

bool compare(student x, student y) {
	if (x.num < y.num) {
		return true;
	}
	else {
		return false;
	}
}

int main() {
	int N;
	cin >> N;

	int M;
	cin >> M;

	vector<student> v;

	int student_num;

	for (int i = 0; i < M; i++) {
		cin >> student_num;

		bool check = false;

		for (int j = 0; j < v.size(); j++) {
			if (student_num == v[j].num) {
				v[j].count++;
				check = true;

				break;
			}
		}

		if (!check) {
			if (v.size() < N) {
				student s;
				s.num = student_num;
				s.count = 1;

				v.push_back(s);
			}
			else {
				int min = v[0].count;

				for (int j = 0; j < v.size(); j++) {
					min = std::min(v[j].count, min);
				}

				for (int j = 0; j < v.size(); j++) {
					if (min == v[j].count) {
						v.erase(v.begin() + j);
						break;
					}
				}
				student s;
				s.num = student_num;
				s.count = 1;

				v.push_back(s);
			}
		}
	}

	sort(v.begin(), v.end(), compare);

	for (int i = 0; i < v.size(); i++) {
		cout << v[i].num << " ";
	}

	return 0;
}