[백준/파이썬] 21939번

📍백준 21939번 문제

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

코드

import heapq
import sys
from collections import defaultdict

input = sys.stdin.readline

minHeap = []
maxHeap = []
solved = defaultdict(int)
n = int(input())

for _ in range(n):
    p, l = map(int, input().split())
    heapq.heappush(minHeap, (l, p))
    heapq.heappush(maxHeap, (-l, -p))

m = int(input())
for _ in range(m):
    command = input().split()

    if command[0] == "recommend":
        # 어려운 문제 추천
        if command[1] == '1':
            while solved[abs(maxHeap[0][1])] != 0:
                solved[abs(maxHeap[0][1])] -= 1
                heapq.heappop(maxHeap)
            print(-maxHeap[0][1])
        # 쉬운 문제 추천
        else:
            while solved[minHeap[0][1]] != 0:
                solved[minHeap[0][1]] -= 1
                heapq.heappop(minHeap)
            print(minHeap[0][1])
    elif command[0] == "add":
        p = int(command[1])
        l = int(command[2])
        heapq.heappush(minHeap, (l, p))
        heapq.heappush(maxHeap, (-l, -p))
    elif command[0] == "solved":
        solved[int(command[1])] += 1

풀이

• 문제 추천 시 어려운 문제와 쉬운 문제 추천이 모두 이루어지므로 minHeap과 maxHeap을 모두 만들어야 한다.
  1. 어려운 문제인 경우
     solved[어려운 문제]가 0이 아닌 경우, 이미 풀었던 문제이므로 maxHeap에서 제거해준다. solved[어려운 문제] = 0 때까지 while문을 돌린다.
  2. 쉬운 문제인 경우
     solved[쉬운 문제]가 0이 아닌 경우, 이미 풀었던 문제이므로 minHeap에서 제거해준다. solved[쉬운 문제] = 0 때까지 while문을 돌린다.
• 풀이된 문제라면 solved[풀이된문제]에 1을 추가해준다.