문제
https://www.acmicpc.net/problem/21939
접근
- 처음 생각한 방법은 딕셔너리에 난이도별로 문제를 저장하려 했으나, 난이도별로 관리할 필요가 없다는 생각이 들어서 우선순위큐로 바꿨다.
- 가장 어려운 문제와 가장 쉬운 문제를 추천해야 하므로 우선순위큐 2개를 사용했고, 푼 문제들을 저장하기 위해 딕셔너리를 사용했다.
- solve 연산을 수행할 때마다 저장된 문제를 갱신하는 방법으로 풀었으나 시간초과가 발생해서 recommend 연산을 수행할 때마다 푼 문제들을 우선순위큐에서 pop하는 방식으로 바꾸었다.
풀이
- 똑같은 문제 번호로 다른 난이도의 문제가 들어올 경우, 이전에 풀었지만 아직 우선순위큐에 남아있는 문제들을 처리해주지 않아 오답
- 따라서 딕셔너리에 문제 번호를 키로 난이도를 값으로 저장해놓고, 푼 문제들은 난이도를 0으로 설정했다.
- recommend 연산이 들어올 때마다 우선순위큐의 첫 원소에 대해 딕셔너리에 저장된 난이도가 해당 문제의 난이도와 같은지 비교해서, 같은 경우 출력하고 다른 경우에는 이미 푼 문제이므로 pop
import heapq, sys
input = sys.stdin.readline
n = int(input())
prob = []
rev_prob = []
solved = dict()
for _ in range(n):
p, l = map(int, input().split())
heapq.heappush(prob, (l, p))
heapq.heappush(rev_prob, (-l, -p))
solved[p] = l
m = int(input())
for _ in range(m):
op, *num = input().rstrip().split()
num = list(map(int, num))
if op == "recommend":
if num[0] == -1:
while prob[0][0] != solved[prob[0][1]]:
heapq.heappop(prob)
print(prob[0][1])
else:
while -rev_prob[0][0] != solved[-rev_prob[0][1]]:
heapq.heappop(rev_prob)
print(-rev_prob[0][1])
elif op == "add":
p, l = num
heapq.heappush(prob, (l, p))
heapq.heappush(rev_prob, (-l, -p))
solved[p] = l
else:
solved[num[0]] = 0
'Python > Coding Test' 카테고리의 다른 글
10165 버스 노선 (0) | 2022.02.17 |
---|---|
2749 피보나치 수 3 (0) | 2022.02.16 |
13334 철로 (0) | 2022.02.15 |
2485 가로수 (0) | 2022.02.14 |
19235 모노미노도미노 (0) | 2022.02.13 |