백준 7662 : 이중 우선순위 큐 (Python)

본문 링크

import sys
input=sys.stdin.readline
import heapq

T=int(input())
for i in range(T):
    K=int(input())

    Q1,Q2=[],[]

    visit=[False]*K

    for j in range(K):

        a,b=input().split()
        if a=="I": #원소 추가
            heapq.heappush(Q1,( int(b) , j))
            heapq.heappush(Q2,( -int(b) , j))
            visit[j]=True #j번째 원소는 존재한다는것을 체크한다.
        else:
            if b=="1": #최대값 삭제
                while Q2 and not visit[Q2[0][1]]:
                    heapq.heappop(Q2)
                if Q2:
                    visit[Q2[0][1]]=False
                    heapq.heappop(Q2)
            else: #최소값 삭제
                while Q1 and not visit[Q1[0][1]]:
                    heapq.heappop(Q1)
                if Q1:
                    visit[Q1[0][1]]=False
                    heapq.heappop(Q1)
    while Q2 and not visit[Q2[0][1]]:
        heapq.heappop(Q2)
    while Q1 and not visit[Q1[0][1]]:
        heapq.heappop(Q1)
    if not Q2 or not Q1: #둘중에 원소가 없다면
        print("EMPTY")
    else:
        print(-Q2[0][0] , Q1[0][0])

📌 어떻게 접근할 것인가?

최대값과 최소값을 찾기 위해서 우선순위 큐를 2개를 사용해야합니다.

하지만 중요한것은 특정 값을 제거할때 최대값 힙에서 값을 제거했다면 똑같이 최소값 힙에서도 값을 제거해줘야 한다는 점입니다.

따라서 방문 체크배열 visit=[False]*K 를 선언해준 후에
원소를 추가할때마다 visit[j]=True , 즉 j번째 원소는 존재한다는 것을 체크 해줍니다.
이후 원소를 삭제할때 visit[Q[0][1]]=False 를 통해서 원소가 삭제됬음을 체크 해줍니다.

따라서 나중에 최대힙에서 원소를 삭제할때 이미 최소힙에서 삭제된 원소라면 그 원소를 최대힙에서도 삭제를 시켜줍니다.

쿼리가 끝난 후에도 최대힙과 최소힙이 다를 수 있으니 한번더 $while$ 문을 통해서 확인 해준후에

만약 최대힙이나 최소힙의 값이 존재 하지 않는다면 EMPTY 를 출력하고
그렇지 않다면 최대힙과 최소힙의 값을 출력해줍니다.