[백준] 21939 문제 추천 시스템 Version1 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/21939
• 🔑 최소 힙, 최대 힙 사용
  • 가장 어려운 문제 추천하기 위한 최대 힙
  • 가장 쉬운 문제 추천하기 위한 최소 힙
  • 💡 solved 명령이 들어오면 바로 빼지 않음
    • solved 1000 명령이라면
    • 문제 리스트에서 1000을 찾고 빼야 하는데 이 과정이 시간 오래 걸림
    • 그래서 solved한 문제는 따로 리스트에 보관하고 추천할 때 solved_list에 있으면 heappop 하는 방식 사용
    • 같은 문제 번호에 다른 난이도가 새로 들어올 수 있으니까 solved_list에는 (문제 번호, 난이도)를 같이 저장해야 함
    • 이때 해당 문제 번호의 난이도를 찾기 위해 딕셔너리를 사용 {문제번호 : 난이도}

 

from heapq import heappop, heappush
import sys
input = sys.stdin.readline

n = int(input())    # 문제 개수

max_q = []      # 최대 힙 (recommend 1)
min_q = []      # 최소 힙 (recommend -1)
problem = {}    # 문제번호 : 난이도
solved_list = []    # 푼 문제

for _ in range(n):
    p, l = map(int, input().split())    # 문제 번호, 난이도
    heappush(max_q, (-l, -p))           # (난이도, 문제번호)
    heappush(min_q, (l, p))             # (난이도, 문제번호)
    problem[p] = l

m = int(input())    # 명령 개수
# p = 문제 번호
# l = 문제 난이도
for _ in range(m):
    command = list(input().split())

    if command[0] == 'recommend':   
        if command[1] == '1':                   # 가장 어려운 문제 추천
            while True:
                l, p = max_q[0]
                if (-p, -l) in solved_list:     # 해결한 문제와 난이도면
                    heappop(max_q)              # 그냥 빼기
                else:                           # 해결 안 한 문제면
                    print(-p)                   # 추천
                    break
        else:                                   # 가장 쉬운 문제 추천
            while True:
                l, p = min_q[0]
                if (p, l) in solved_list:       # 해결한 문제와 난이도면
                    heappop(min_q)              # 그냥 빼기
                else:                           # 해결 안 한 문제면
                    print(p)                    # 추천
                    break
    elif command[0] == 'add':                   # 문제 추가 명령
        p, l = int(command[1]), int(command[2])
        heappush(max_q, (-l, -p))               # (난이도, 문제번호)
        heappush(min_q, (l, p))                 # (난이도, 문제번호)
        problem[p] = l
    elif command[0] == 'solved':                # 문제 해결 명령
        p = int(command[1])
        l = problem[p]
        solved_list.append((p, l))