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

문제 링크

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

 

문제

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

 

예제 입력 1

5
1000 1
1001 2
19998 78
2667 37
2042 55
8
add 1402 59
recommend 1
solved 1000
solved 19998
recommend 1
recommend -1
solved 1001
recommend -1

예제 출력 1

19998
1402
1001
2667

 

알고리즘 분류

• 자료 구조

 

풀이

이 문제는 Set에 원소를 추가 및 삭제하는 쿼리문이 최대 10,000번까지 나올 수 있는데, 문제의 개수는 최대 100,000개이다. 따라서 O(nlogn)의 시간복잡도로 해결하는 것이 좋아보인다.

우선순위 큐를 생각했으나, 우선순위 큐로는 문제를 제거하기가 힘들었고, 찾아본 결과 Set을 활용하는 것이 더 좋다는 생각이 들어 Set을 활용하였다.

Set에는 Pair를 저장하는데, Pair(문제의 난이도, 문제 번호)를 저장한다. 또한 MultiSet 아니고 Set을 사용하면 O(logn)으로 정렬이 가능하다.

문제를 제거할 때에는 find() 함수로 Pair(문제의 난이도, 문제 번호)를 찾아 제거하는데, 이 때 문제 번호의 난이도를 기록하기 위해 Map을 활용한다.

가장 어려운, 혹은 쉬운 문제를 탐색하기 위해서 begin(), rbegin()을 활용한다. 문제의 난이도가 정렬 우선순위가 높기 때문에 먼저 문제의 난이도 순으로 오름차순 정렬되고, 그 이후에 문제 번호를 기준으로 오름차순 정렬하기 때문에 begin()이 가리키는 문제는 문제의 난이도가 가장 낮으며 문제 번호도 가장 낮은 문제이며, rbegin()이 가리키는 문제는 문제의 난이도가 가장 높고 문제 번호도 가장 높은 문제이다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <set>
#include <algorithm>
#define MAX 100001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M, X, P, L;
string S;
unordered_map<int, int> Levels;
set<pair<int, int> > Problems;

void recommend() {
	if (X == 1) {
		cout << Problems.rbegin()->second << "\n";
	}
	else if (X == -1) {
		cout << Problems.begin()->second << "\n";
	}
}

void add() {
	Levels[P] = L;
	Problems.insert(make_pair(L, P));
}

void solved() {
	auto IT = Problems.find(make_pair(Levels[P], P));
	if (IT != Problems.end()) {
		Problems.erase(IT);
	}
}

void input() {
	cin >> N;
	while (N--) {
		cin >> P >> L;
		add();
	}
	cin >> M;
	while (M--) {
		cin >> S;
		if (S == "recommend") {
			cin >> X;
			recommend();
		}
		else if (S == "add") {
			cin >> P >> L;
			add();
		}
		else if (S == "solved") {
			cin >> P;
			solved();
		}
	}
}

int main() {
    FASTIO

	input();

    return 0;
}