[BOJ] 1713 후보 추천하기

1. 문제 요약

추천 받은 학생의 사진을 전시하기 위한
N
개의 사진틀이 있다. 총 추천 횟수
totalRecNum
가 주어지면
totalRecNum
개의 추천을 고려하여 최종적으로 사진틀에 걸리게 되는 학생의 번호를 오름차순으로 출력한다. 사진틀에 걸리게/내려오게 되는 기준은 아래와 같다.

초기 사진틀은 모두 비어 있다.

추천받은 시점에서 해당 학생은 무조건 사진틀에 게시된다.

비어있는 사진틀이 없다면 사진틀에 있는 학생 중 추천 수가 가장 적은 학생을 내린다. 만약 그런 학생이 두 명 이상 있다면, 가장 오래된 사진을 내린다. 이 경우, 내려가는 학생의 추천수는 0이 된다.

이미 게시된 학생의 경우에는 추천수만 증가한다.

1 <= N <= 20

totalRecNum <= 1,000

1 <= studentNum <= 100

2. 풀이 정리

그냥 깡 시뮬레이션 문제인 것 같았다.

현재 사진틀의 상태를 저장하기 위한 vector frame을 선언하고,
N
크기로 resize했다.
- frame에는 학생들의 번호를 저장할 것이다.
- 가장 오래된 사진을 0번 인덱스에 저장하고, 최근에 걸린 사진을 뒤로 저장한다.
totalRecNum
만큼
curStudentNum
을 입력받는다.
우선
curStudentNum
에 해당하는 학생은 무조건 사진틀에 걸리기 때문에, 추천수를 +1해준다.
- 그리고 다음 세 경우를 체크한다.
1. 만약 아무 사진도 걸려 있지 않다면 해당 사진을 걸어놓는다.
2. 사진틀 자리가 남아있는 경우,
  1. 해당 학생 사진이 걸려 있다면 패스한다.
  2. 걸려 있지 않다면 사진을 걸어 준다.
3. 사진틀 자리가 없는 경우
  1. 해당 학생 사진이 걸려 있다면 패스한다.
  2. 걸려 있지 않다면 가장 추천수가 낮으면서 오래된 사진을 찾는다.
  3. 해당 사진을 없애면서 뒷 번호 사진들을 한 칸 씩 앞으로 밀어준다.
  4. 마지막 자리에
    curStudentNum
    의 사진을 걸어 준다.
frame을 오름차순으로 정렬한 다음, 출력한다.
- 만약 추천받은 학생이 사진틀 수보다 적으면 frame에 0값이 들어있을 수 있다.
- 따라서 0은 출력하지 않아야 한다.

3. 구현

#include <iostream>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;

int N, totalRecNum, curStudentNum;
vector<int> frame;
int cnt[1005];
int MAX = 1001;

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

	cin >> N;
	cin >> totalRecNum;
	frame.resize(N);

	int top = 0;

	for (int i = 0; i < totalRecNum; i++) {
		cin >> curStudentNum;
		cnt[curStudentNum]++;
		
		// 사진이 없는 경우 무조건 사진을 걸어준다.
		if (top == 0) {
			frame[top++] = curStudentNum;
			continue;
		}

		// 사진이 걸려있는지 확인한다.
		bool found = false;
		for (int j = 0; j < top; j++) {
			if (frame[j] == curStudentNum) {
				found = true;
				break;
			}
		}

		// 사진틀 자리가 남아있는 경우
		// 해당 학생의 사진이 이미 걸려있다면 넘어가고,
		// 걸려있지 않다면 해당 사진을 걸어준다.
		if (top < N) {
			if (!found)
				frame[top++] = curStudentNum;
			continue;
		}

		// 사진틀 자리가 남아있지 않으면서 해당 학생의 사진이 걸려 있지 않은 경우
		if (!found) {
			int minCnt = MAX;
			int idx = -1;

			for (int j = 0; j < top; j++) {
				if (frame[j] == 0) continue;
				if (cnt[frame[j]] < minCnt) {
					minCnt = cnt[frame[j]];
					idx = j;
				}
			}

			cnt[frame[idx]] = 0;
			for (int j = 0; j < top; j++)
				if (j > idx && j > 0)
					frame[j - 1] = frame[j];
			frame[N - 1] = curStudentNum;
		}
	}

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

	for (int idx : frame)
		if (idx != 0)
			cout << idx << " ";

	return 0;
}

[BOJ] 1713 후보 추천하기

Table Of Contents

1. 문제 요약

2. 풀이 정리

3. 구현