[백준] 7662. 이중우선순위큐

시간초과때문에 heapq를 사용해야 시간을 단축시킬 수 있다.

list로 하면 시간복잡도가 O(n)인데

heapq로 하면 O(log2n)이라서 heapq로 최소힙, 최대힙 따로 만들어서 해야함

import heapq
import sys
t=int(sys.stdin.readline())
for i in range(t):
    n=int(sys.stdin.readline())
    minqueue=[] #최소 힙
    maxqueue=[] #최대 힙
    visited=[0]*n
    for j in range(n):
        pqueue=sys.stdin.readline().rstrip()
        if pqueue.split()[0]=='I':
            x=int(pqueue.split()[1])
            heapq.heappush(minqueue,(x,j))
            heapq.heappush(maxqueue,(-x,j)) #x를 -x로 바꿔야 heappop했을 때 최대값 나옴
            visited[j]=1 #방문 표시
        elif pqueue=='D -1': #최소값 삭제
            while minqueue and not visited[minqueue[0][1]]: #maxqueue에서 사라진 값 삭제
                heapq.heappop(minqueue)
            if minqueue:
                visited[minqueue[0][1]]=0
                heapq.heappop(minqueue)
        elif pqueue=='D 1': #최대값 삭제
            while maxqueue and not visited[maxqueue[0][1]]: #minqueue에서 사라진값 삭제
                heapq.heappop(maxqueue)
            if maxqueue:
                visited[maxqueue[0][1]]=0
                heapq.heappop(maxqueue)

    while minqueue and not visited[minqueue[0][1]]:
        heapq.heappop(minqueue)
    while maxqueue and not visited[maxqueue[0][1]]:
        heapq.heappop(maxqueue)

    if not maxqueue or not minqueue:
        print("EMPTY")
    else:
        print(-maxqueue[0][0],minqueue[0][0])