[백준 21939] 문제 추천 시스템 Version 1 (C++)

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

21939번: 문제 추천 시스템 Version 1

문제

---

tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다.

깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다.

만들려고 하는 명령어는 총 3가지가 있다. 아래 표는 각 명령어에 대한 설명이다.

recommend x	x가 1인 경우 추천 문제 리스트에서 가장 어려운 문제의 번호를 출력한다. 만약 가장 어려운 문제가 여러 개라면 문제 번호가 큰 것으로 출력한다.  x가 -1인 경우 추천 문제 리스트에서 가장 쉬운 문제의 번호를 출력한다. 만약 가장 쉬운 문제가 여러 개라면 문제 번호가 작은 것으로 출력한다.
add P L	추천 문제 리스트에 난이도가 L인 문제 번호 P를 추가한다. (추천 문제 리스트에 없는 문제 번호 P만 입력으로 주어진다. 이전에 추천 문제 리스트에 있던 문제 번호가 다른 난이도로 다시 들어 올 수 있다.)
solved P	추천 문제 리스트에서 문제 번호 P를 제거한다. (추천 문제 리스트에 있는 문제 번호 P만 입력으로 주어진다.)

명령어 recommend는 추천 문제 리스트에 문제가 하나 이상 있을 때만 주어진다.

명령어 solved는 추천 문제 리스트에 문제 번호가 하나 이상 있을 때만 주어진다.

위 명령어들을 수행하는 추천 시스템을 만들어보자.

 

입력

---

첫 번째 줄에 추천 문제 리스트에 있는 문제의 개수 N가 주어진다.

두 번째 줄부터 N + 1줄까지 문제 번호 P와 난이도 L가 공백으로 구분되어 주어진다.

N + 2줄은 입력될 명령문의 개수 M이 주어진다.

그 다음줄부터 M개의 위에서 설명한 명령문이 입력된다.

 

출력

---

recommend 명령이 주어질 때마다 문제 번호를 한 줄씩 출력한다. 최소 한번의 recommend 명령어가 들어온다.

 

제한

---

•  1 ≤ N,P ≤ 100,000
•  1 ≤ M ≤ 10,000
•  1 ≤ L ≤ 100, L은 자연수
• x=±1

문제 풀이

---

map과 우선순위 큐를 이용하는 문제.

문제를 <문제 번호, 난이도를 저장하는 set>으로 구성되는 map에 저장하여 같은 문제의 다른 난이도를 모두 저장할 수 있도록 한다.

또한 가장 어려운 난이도의 문제 순으로 정렬하는 우선순위 큐와 가장 쉬운 난이도의 문제 순으로 정렬하는 우선순위 큐 2개를 만들어 두 난이도에 대해 추천을 받을 수 있도록 한다. 큐에 있는 원소들은 top에 있는 원소를 제외하고 중간 삭제가 불가능하므로 top에 해당하는 원소가 현재 문제를 저장하는 map에 있는지 확인한다. map에 있더라도 solved 명령을 통해 이미 지워진 난이도일 수도 있으므로 이에 대한 확인 역시 필요하다.

 

아래는 코드.

#include <iostream>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <utility>
using namespace std;
map<int, set<int>> problems;
map<int, set<int>>::iterator it;

struct hardCmp
{
	bool operator()(pair<int, int>& p1, pair<int, int>& p2)
	{
		if (p1.first > p2.first)
		{
			return false;
		}
		else if (p1.first == p2.first)
		{
			return p1.second < p2.second;
		}
		else
		{
			return true;
		}
	}
};

struct easyCmp
{
	bool operator()(pair<int, int>& p1, pair<int, int>& p2)
	{
		if (p1.first < p2.first)
		{
			return false;
		}
		else if (p1.first == p2.first)
		{
			return p1.second > p2.second;
		}
		else
		{
			return true;
		}
	}
};

priority_queue<pair<int, int>, vector<pair<int, int>>, hardCmp> hardProblemQueue;
priority_queue<pair<int, int>, vector<pair<int, int>>, easyCmp> easyProblemQueue;

void addProblem(int problemNum, int difficulty)
{
	it = problems.find(problemNum);
	if (it == problems.end())
	{
		set<int> s;
		s.insert(difficulty);
		problems.insert({ problemNum, s });
	}
	else
	{
		it->second.insert(difficulty);
	}
	hardProblemQueue.push(make_pair(difficulty, problemNum));
	easyProblemQueue.push(make_pair(difficulty, problemNum));
}

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

	int N, M;
	int problemNum, difficulty, flag;
	string query;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> problemNum >> difficulty;
		addProblem(problemNum, difficulty);
	}
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		cin >> query;
		if (query == "add")
		{
			cin >> problemNum >> difficulty;
			addProblem(problemNum, difficulty);
		}
		else if (query == "recommend")
		{
			cin >> flag;
			if (flag == 1)
			{
				while (true)
				{
					pair<int, int> top = hardProblemQueue.top();
					it = problems.find(top.second);
					if (it == problems.end())
					{
						hardProblemQueue.pop();
					}
					else
					{
						set<int> problemDifficulty = it->second;
						if (problemDifficulty.find(top.first) == problemDifficulty.end())
						{
							hardProblemQueue.pop();
						}
						else
						{
							cout << top.second << "\n";
							break;
						}
					}
				}
			}
			else
			{
				while (true)
				{
					pair<int, int> top = easyProblemQueue.top();
					it = problems.find(top.second);
					if (it == problems.end())
					{
						easyProblemQueue.pop();
					}
					else
					{
						set<int> problemDifficulty = it->second;
						if (problemDifficulty.find(top.first) == problemDifficulty.end())
						{
							easyProblemQueue.pop();
						}
						else
						{
							cout << top.second << "\n";
							break;
						}
					}
				}
			}
		}
		else
		{
			cin >> problemNum;
			problems.erase(problemNum);
		}
	}
	return 0;
}