https://www.acmicpc.net/problem/21939
21939번: 문제 추천 시스템 Version 1
tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다. 깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다. 만들려고 하는 명령
www.acmicpc.net
recommend x
x가 1인 경우 리스트에서 가장 어려운 문제의 번호를 출력, 가장 어려운 문제가 여러 개면 문제 번호가 큰 것을 출력
x가 -1인 경우 리스트에서 가장 쉬운 문제의 번호를 출력, 가장 어려운 문제가 여러 개면 문제 번호가 작은 것을 출력
add P L
리스트에 난이도가 L인 문제 번호 P를 추가한다.
현재 리스트에 없는 문제만 들어오며, 이미 해결하여 리스트에서 제외된 문제가 다시 들어올 수 있다.
solved P
리스트에서 문제 번호 P를 제거한다. (해결한 것으로 간주)
문제들은 [문제 번호, 난이도] 로 정리되어 있으며, 들어온 순서대로 명령을 처리하는 문제입니다.
recommend 명령어에서 난이도가 가장 어려운 문제와 가장 쉬운 문제를 빠르게 뽑아내야 하므로 우선 순위 큐를 2개 사용하며, 최대 우선순위 큐와 최소 우선순위 큐를 같이 관리합니다.
각 문제의 난이도를 나타내기 위해 levellist라는 배열을 사용하였으며, 값이 0이 아니라면 리스트에 있는 문제라는 뜻입니다.
이를 이용하여 solved 시 levellist의 값을 0으로 바꾸고, recommend 명령어가 들어왔을 때 출력하기 전에 현재 최대/최소 우선순위 큐에 이미 solved된 문제가 있는지 확인하는 작업을 거친 후에 출력하도록 합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
#include <iostream>
#include <queue>
#include <algorithm>
#include <set>
#include <string>
#define MAX 100001
using namespace std;
typedef pair<int, int> pi;
priority_queue<pi, vector<pi>, less<pi> > mxq;
priority_queue<pi, vector<pi>, greater<pi> > mnq;
int levellist[MAX];
int N, M;
void func() {
string type;
int x, y;
cin >> M;
while (M--) {
cin >> type;
if (type == "add") {
cin >> x >> y;
mxq.push({ y,x });
mnq.push({ y,x });
levellist[x] = y;
}
else {
cin >> x;
if (type == "recommend") {
if (x == 1) {
while (1) {
int p = mxq.top().second;
int l = mxq.top().first;
if (levellist[p] == l) break;
mxq.pop();
}
cout << mxq.top().second << '\n';
}
else {
while (1) {
int p = mnq.top().second;
int l = mnq.top().first;
if (levellist[p] == l) break;
mnq.pop();
}
cout << mnq.top().second << '\n';
}
}
else {
levellist[x] = 0;
}
}
}
}
void input() {
int P, L;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> P >> L;
mxq.push({ L,P });
mnq.push({ L,P });
levellist[P] = L;
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > data-structure' 카테고리의 다른 글
| boj 15926 현욱은 괄호왕이야!! (1) | 2023.07.24 |
|---|---|
| boj 17299 오등큰수 (0) | 2021.02.22 |
| boj 9372 상근이의 여행 (0) | 2021.02.09 |
| boj 1158 요세푸스 문제 (0) | 2021.02.09 |
| boj 1918 후위 표기식 (0) | 2021.02.05 |