C++ / 백준 / 21939 / 문제 추첨 시스템 Version 1

문제

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

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

문제풀이

map과 multiset을 이용한다

multiset은 난이도가 같으면 문제 번호가 높은 순, 난도가 다르면 난이도가 높은 순부터 낮은 수로 정렬하도록 cmp를 따로 만들었다. (내림차순)

문제 번호와 난이도를 입력받으면 multiset, map에 집어넣는다.

recommend 1을 입력받으면 iterator가 multiset의 처음을 가리키게 되고 문제 번호를 출력하기 위해 iter->first를 출력한다.

recommend -1을 입력받으면 반대로 iterator가 입력의 끝(end바로 직전)을 가리키도록 한 후 first값을 출력한다.

add를 입력받으면 처음 입력받을 때처럼 multiset과 map에 집어넣는다.

마지막으로 solved P를 입력받으면 map을 이용해 해당 문제의 난이도를 알아낸 후 multiset과 map에서 그 값을 erase 한다.

 

코드

#include <iostream>
#include <set>
#include <map>
using namespace std;

struct cmp {
	bool operator()(const pair<int, int>& a, const pair<int, int>& b) const {
		if (a.second == b.second)
			return a.first > b.first;

		else
			return a.second > b.second;
	}
};


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

	int N(0), M(0);
	int idx(0);

	map<int, int>m;
	multiset<pair<int, int>, cmp>problem;	
	multiset<pair<int, int>, cmp>::iterator iter;

	int number(0), level(0);
	string cmd("");

	cin >> N;

	for (idx = 0; idx < N; ++idx) {
		cin >> number >> level;
		problem.insert({ number, level });
		m.insert({ number, level });
	}
	
	cin >> M;

	for (idx = 0; idx < M; ++idx) {
		cin >> cmd;
		if (cmd == "recommend") {
			cin >> number;
			if (number == 1) {
				iter = problem.begin();
				cout << iter->first;
			}
			else {
				iter = --problem.end();
				cout << iter->first;
			}
			cout << '\n';
		}
		else if (cmd == "add") {
			cin >> number >> level;
			problem.insert({ number, level });
			m.insert({ number,level });
		}
		else {
			cin >> number;
			level = m[number];			
			problem.erase({number, level});
			m.erase(number);
		}
	}	
}