1. 문제 분석하기

1.1. 문제 의도

• 문제를 잘 읽고 조건을 빠짐없이 구현하는 구현, 시뮬레이션 문제입니다.

1.2. 문제 조건

1. 처음 모든 사진틀 비어있다.
2. 빈 사진틀 없는 경우, 게시된 후보들 중 추천수가 가장 낮고 게시된 지 오래된 순으로 교체한다.
3. 학생은 총 100명있다.
4. 답은 학생 번호의 오름차순으로 출력한다.

2. 문제 해결하기

• 문제 조건에 따라 빠짐없이 구현하면 되는 간단한 문제입니다.
• 학생에 대한 구조체를 만들고 ‘학생 번호’, ‘추천수’, ‘게시된 시간’을 저장합니다.
• 추천학생 번호를 입력받을 때
  • 아직 빈 사진틀이 있다면 삽입합니다.
  • 빈 사진틀이 없다면, std::min_element() 함수를 이용하고 comparator로 람다함수를 정의해서 사용자 정의 구조체에 대해서도 작동하도록 만듭니다.
  • 가장 추천수가 낮고, 게시된 지 오래된 원소를 찾았다면, 방금 입력받은 번호로 교체합니다.
• 답을 출력하기 위해 std::sort() 함수를 이용합니다.

3. 코드

#include <iostream>
#include <vector>
#include <algorithm>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;

typedef struct cand {
	int num, time, good;
	bool operator == (int n) { return this->num == n; }
}cand;

int main() {
    ios::sync_with_stdio(false), cin.tie(NULL);
    int N;
    cin >> N;
    vector<cand> frame;
    
    int K;
    cin >> K;
    for (int t = 0; t < K; ++t) {
    	int n;
    	cin >> n;
		// 추천 수 하나 증가.
		auto target = find(frame.begin(), frame.end(), n);
		if (target != frame.end()) { target->good++; continue; }
    	// 남은 틀이 있는 경우 단순 삽입.
    	if (frame.size() < N) { frame.push_back({n, t, 1}); continue; }
		// 삭제할 사람 고르고 갱신.
		target = min_element(frame.begin(), frame.end(), [](cand lhs, cand rhs){
			if (lhs.good == rhs.good) return lhs.time < rhs.time;
			return lhs.good < rhs.good;	
		});
		*target = {n, t, 1};
	}
	sort(frame.begin(), frame.end(), [](cand lhs, cand rhs){ return lhs.num < rhs.num; });
	
	int prev = 0;
	for (const auto& i : frame)
		if (prev != i.num) prev = i.num, cout << i.num << ' '; 
}

4. 결과