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

 

www.acmicpc.net/problem/1713

1713번: 후보 추천하기

[문제 풀이]

단순 구현을 통해 문제를 해결했습니다.

 

이 문제의 경우 스케줄러를 구현하는 것과 비슷한 형태였습니다.

문제를 해결하기 위해 사진틀을 map을 통해 구현하였습니다.

N(사진틀)의 범위가 20 이하이므로 추천 횟수 하나마다 map을 순회하는 형식으로 구현하였습니다.

[코드]

#include<iostream>
#include<map>

using namespace std;

map<int, pair<int, int>> LRU;

int N, M;

int main() {

	scanf("%d %d", &N, &M);

	for (int i = 1; i <= M; i++) {

		int temp;

		scanf("%d", &temp);

		if (LRU.find(temp) == LRU.end()) {

			if (LRU.size() < N) {//사진틀이 N보다 작은 경우 
				LRU[temp].first = 1;
				LRU[temp].second = i;
			}
			else {
				pair<int, int> record;
				int index = LRU.begin() -> first;
				record = LRU.begin() -> second;

				for (auto item : LRU) {
					if (item.second < record) {
						index = item.first;
						record = item.second;
					}
				}
				LRU.erase(index);
				LRU[temp].first = 1;
				LRU[temp].second = i;

			}
		}
		else {
			LRU[temp].first++;
		}
	}

	for (auto item : LRU) {
		printf("%d ", item.first); 
	}

	return 0;
}