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

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

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

 

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

int a, b;
set<pair<int, int>> s;
map<int, int> m;

int main() {
	cin >> a;
	for (int i = 0; i < a; i++) {
		int p, l;
		cin >> p >> l;
		s.insert({ l, p });
		m[p] = l;
	}
	cin >> b;
	for (int i = 0; i < b; i++) {
		string command;
		cin >> command;
		if (command == "recommend") {
			int x;
			cin >> x;
			if (x == 1) {
				auto it = s.rbegin();
				cout << it->second << '\n';
			}
			else if (x == -1) {
				auto it = s.begin();
				cout << it->second << '\n';
			}
		}
		else if (command == "add") {
			int p, l;
			cin >> p >> l;
			s.insert({ l, p });
			m[p] = l;
		}
		else if (command == "solved") {
			int p;
			cin >> p;
			s.erase({ m[p], p });
		}
	}
	return 0;
}

 

set과 map으로 풀었다.

 

set은 이진탐색트리 구조로 자동으로 정렬을 해주며, 정렬 속도가 엄청나게 빠르다.

"solved"에서 들어오는 정보가 문제 번호밖에 없으므로, 문제 번호를 알고 있다면 바로 난이도를 알아낼 수 있도록 map을 사용한다.

 

 

***

s.end() -> 맨 마지막 원소의 다음 가리킴

s.rbegin() -> 맨 마지막 원소 가리킴