[C++] 백준 1713번: 후보 추천하기

문제 링크

1713번: 후보 추천하기

문제 요약

N개의 사진틀이 있고, 다음 규칙에 따라서 사진을 게시한다.

1. 학생들이 추천을 시작하기 전에 모든 사진틀은 비어있다.
2. 어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다.
3. 비어있는 사진틀이 없는 경우에는 현재까지 추천 받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 자리에 새롭게 추천받은 학생의 사진을 게시한다. 이때, 현재까지 추천 받은 횟수가 가장 적은 학생이 두 명 이상일 경우에는 그러한 학생들 중 게시된 지 가장 오래된 사진을 삭제한다.
4. 현재 사진이 게시된 학생이 다른 학생의 추천을 받은 경우에는 추천받은 횟수만 증가시킨다.
   사진틀에 게시된 사진이 삭제되는 경우에는 해당 학생이 추천받은 횟수는 0으로 바뀐다.

마지막에 사진틀에 게시되어 있는 후보들의 번호를 오름차순으로 출력해야 한다.

접근 방법

엄청 쉬운 구현 문제였는데, 문제를 잘못 읽어서 두 번 틀렸습니다. 이미 갱신된 후보가 추천될 때, 추천받은 시간도 같이 갱신하는 실수를 저질렀습니다.

자료구조를 사용하면 편한데, 우선순위큐와 맵 중에 고민하다가 맵을 쓰는 쪽이 더 쉽게 나올거 같아서 그냥 맵을 사용했습니다.

1. 후보 번호를 입력 받았을 때, 맵 내부에 있으면 추천 횟수를 1 증가시킨다.
2. 맵 내부에 없고, 맵의 크기가 N보다 작다면 맵에 삽입한다.
3. 그 외의 경우에는 맵에서 추천 횟수가 가장 적은 후보들 중에 가장 추천 받은지 오래된 후보를 삭제하고 새로운 후보를 삽입한다.

문제 크기가 작고 요구사항도 간단해서 어떻게 풀어도 풀릴거 같습니다. 다만 저는 맵이 풀이가 더 편하게 나올거 같아서 맵으로 풀었습니다.

코드

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	int n, k;
	cin >> n >> k;

	map<int, pair<int, int>> m;
	for (int i = 0; i < k; i++)
	{
		int r;
		cin >> r;

		if (m.find(r) != m.end())
			m[r].first++;
		else if (m.size() < n)
			m.insert({ r, {1, i} });
		else
		{
			int num = 0, rec = INT_MAX, last = INT_MAX;
			for (auto& j : m)
			{
				if (j.second.first < rec || (j.second.first == rec && j.second.second < last))
				{
					num = j.first;
					rec = j.second.first;
					last = j.second.second;
				}
			}

			m.erase(num);
			m.insert({ r, {1, i} });
		}
	}

	for (auto& i : m)
		cout << i.first << ' ';
	return 0;
}