[KOI 2007 초등부 1번] 백준 1713번 후보 추천하기 문제 풀이

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

1713번: 후보 추천하기

한국정보올림피아드 초등부 2007년도 전국본선 1번문제이자 백준 1713번 문제 "후보 추천하기" 문제 풀이입니다.

 

문제 개요

정올 초등부 1번문제 치고는 solved.ac 티어가 골드5 로 높은 편입니다.

문제 내용을 보면, 약간 특이한 룰을 따라서 코딩을 해야 합니다. 시뮬레이션 종류의 문제로 볼 수 있습니다.

 

LRU Cache 구현하는 것 같은 느낌이고, 사진 틀에 학생 사진을 넣고 빼는 것을 잘 시뮬레이션 해야 합니다.

 

특히나 중요한 부분은 사진 틀이 꽉 찼을 때 어떤 녀석을 빼느냐에 관한 문제인 것 같은데, 사진 틀의 개수가 최대 20개 밖에 되지 않으니, 뺄 녀석을 그때 그때 모든 사진 틀을 다 순회하면서 체크하면 될 것 같습니다.

 

총 추천회수는 1000이니, 최악의 경우 계산량은 //(1000*20//)으로 2만 정도가 됩니다.

시간복잡도는 크게 문제가 되지는 않을 것 같습니다.

 

사진 틀에서 삭제되는 경우, 추천 수가 0이 되는 것은 사진틀에서 뺀 경우 추천 수를 트래킹 하지 않으면 되므로 구현을 더 간단하게 해 줍니다.

 

구현전략

사진틀에서 가장 추천 수가 적거나, 추천수가 같다면 더 오래된 녀석을 빼야 한다." 이 조건을 쉽게 하도록 구현을 해야하는데, pair<int, int>를 사용하면 편할 듯 합니다.

 

C++ STL에 있는 pair은 비교 연산자가 기본적으로 first끼리 비교하고, first가 같다면 second끼리 비교하는 탬플릿 구조체입니다.

template class<T1, T2>
class pair {
	T1 first;
    T2 second;
    bool operator<(const class pair& rhs) const {
    	if (first != rhs.first) {
        	return first < rhs.first;
        }
        return second < rhs.second;
    };
    bool operator>(const class pair& rhs) const {
    	if (first != rhs.first) {
        	return first > rhs.first;
        }
        return second > rhs.second;
    }
};

대략 위와 같은 형태라고 보시면 됩니다.

 

따라서 first에 투표 수, second에 추가한 시기를 넣으면, pair값이 최소인녀석을 제거하면 되는 형식입니다.

 

코드

 

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
map<int, pii> slot; //pii.first = vote , pii.second = age

int main() {
	int n, k;
	int cnt = 0;
	cin >> n >> k;
	for (int i = 1; i <= k; i++) {
		int tmp;
		cin >> tmp;
		(void)0;
		if (slot.find(tmp) == slot.end()) {
			//기존에 없는 경우
			if (slot.size() < n) {
				slot[tmp].first = 1;
				slot[tmp].second = i;
			}
			else {
				//기존거 지우고
				int victim = slot.begin()->first;
				pii value = slot.begin()->second;
				for (auto a : slot) {
					if (a.second < value) {
						value = a.second;
						victim = a.first;
					}
				}
				slot.erase(victim);
				slot[tmp].first = 1;
				slot[tmp].second = i;
			}
		}
		else {
			//있는 경우 투표만 추가시킨다.
			slot[tmp].first = slot[tmp].first + 1;
		}
	}
	for (auto it : slot) {
		printf("%d ", it.first);
	}
	return 0;
}