[백준] 21939 문제 추천 시스템 Version 1 python

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

21939번: 문제 추천 시스템 Version 1

두 개의 힙(최대힙, 최소힙)을 사용해서 최대값 최솟값을 같이 파악하고, 출력할때 힙에서 제거했던 값이면 빼내는 방법으로 진행한다. 

 한번 제거했다가 같은 문제번호가 난이도가 바뀌어서 추가하는 경우 따로 처리해줘야했는데 level이라는 딕셔너리를 사용해서 현재의 난이도를 추적할수 있도록 했다.(힙에 같은 문제로 이전 난이도를 가지고 있다면 제거할수 있도록)

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

def main():
    N = int(input())
    min_h, max_h = [], []
    level = {}
    for _ in range(N):
        P, L = map(int, input().split())
        heappush(min_h, (L, P))
        heappush(max_h, (-L, -P))
        if not level.get(P):
            level[P] = 0
        level[P] = L


    M = int(input())
    for _ in range(M):
        c, *args = input().split()
        if c[0] == 'a':
            P, L = map(int, args)
            heappush(min_h, (L, P))
            heappush(max_h, (-L, -P))
            if not level.get(P):
                level[P] = 0
            level[P] = L
        elif c[0] == 's':
            P = int(args[0])
            level[P] = 0
        else: #if c == "recommend"
            x = args[0]
            if x == '1': # max level
                while max_h and level[-max_h[0][1]] != -max_h[0][0]:
                    heappop(max_h)
                print(-max_h[0][1])
            else: # x == -1
                while min_h and level[min_h[0][1]] != min_h[0][0]:
                    heappop(min_h)
                print(min_h[0][1])


if __name__ == "__main__":
    main()