BOJ : 1713 후보 추천하기

---

[BOJ 1713(S1)리뷰]

시뮬레이션 문제다. 문제를 이해한 후에 적당한 자료구조를 이용하여 구현하면 된다.

나는 벡터를 이용하여 추천수와,학생 번호를 저장하고 사진틀에 올라간 학생들의 인덱스를 따로 기록해 놓았다.

학생번호 입력이 들어올 때 마다 해당 학생이 사진틀에 존재하는지 확인하고 다음의 과정을 거친다.

1. 사진틀에 존재하지 않는다면
- 사진틀에 공간이 있는지 확인하고 비어있다면 학생번호를 기록하고, 학생을 사진틀에 추가한다.
- 사진틀에 공간이 없다면 추천수가 가장 낮은 학생의 사진틀을 삭제하고 추가한다.

2. 사진틀에 존재한다면
- 미리 기록해둔 인덱스를 통하여 벡터에 접근해 추천수를 증가시킨다.

이 과정을 순서대로 진행한 후에 최종적으로 벡터에 남은 값을 학생 번호를 기준으로 오름차순으로 정렬하여 출력하면 정답처리를 받을 수 있다.

/*
	21.01.11
	BOJ : 1713 후보 추천하기 (https://www.acmicpc.net/problem/1713)
	구현/시뮬레이션
*/
#include <bits/stdc++.h>
using namespace std;

int N, C;
int idx[101] = { 0 };
vector <pair<int,int>> tle;

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N >> C;

	fill(idx, idx + 101, -1);

	for (int i = 0; i < C; i++) {
		int n;
		cin >> n;

		if (idx[n] == -1) { //해당 학생이 사진틀에 없음.
			//사진틀의 크기 확인하고 넣기
			if (tle.size() >= N) { //꽉참
				int len = tle.size();
				int min_idx=-1;
				int min_val = INT_MAX;
				for (int j = 0; j < len; j++) {
					if (tle[j].second < min_val) {
						min_val = tle[j].second;
						min_idx = j;
					}
				}

				idx[tle[min_idx].first] = -1;
				tle.erase(tle.begin()+min_idx);

				for (int j = 0; j < len - 1; j++) {
					idx[tle[j].first] = j;
				}

				tle.push_back({ n,1 });
				idx[n] = tle.size() - 1;
			}
			else { //비어있음
				tle.push_back({n,1});
				idx[n] = tle.size() - 1;
			}
		}
		else { //사진틀에 이미 있음
			//인덱스로 접근해 추천수 증가시키기
			tle[idx[n]].second++;
		}
	}

	sort(tle.begin(), tle.end());

	for (auto c : tle) {
		cout << c.first << " ";
	}

	return 0;
}