문제

문제 링크 : https://www.acmicpc.net/problem/7662

풀이

평범한 우선순위 큐는 최솟값 또는 최댓값만 신경쓰면 되지만, 이중 우선순위 큐는 최솟값과 최댓값 둘 다 신경써야 한다.

여러 방법을 시도해봤는데 전부 시간 초과가 떠서 구글링을 통해 찾은 풀이 방법을 이용해서 풀었다.

우선 최소 힙과 최대 힙을 선언한다. 그리고 I 명령어가 입력되면 숫자를 최소 힙과 최대 힙에 넣어주는데, 이때 해당 숫자의 id값도 같이 넣어준다. visited 리스트의 id번째 값을 True로 바꿔준다.

'D -1' 명령어가 들어오면 최솟값을, 'D 1' 명령어가 들어오면 최댓값을 삭제해야 한다. 지우고자 하는 값의 id값을 visited 리스트에 넣고 값이 무엇인지 확인한다. 만약에 False가 나온다면 해당 값은 이미 삭제된 값이므로 다음 값을 검사한다. 이 과정을 visited 리스트의 값이 True가 나올 때까지 반복해준다.

이후엔 해당 id의 visited 리스트 값을 False로 바꿔주고 힙에서 해당 값을 삭제해준다.

이를 명령어가 끝날 때까지 반복한다.

import sys
import heapq
input = sys.stdin.readline

t = int(input())

for _ in range(t):
    minHeap = []
    maxHeap = []
    k = int(input())
    id = 0
    visited = [False] * 1000001
    for i in range(k):
        cmd = input().rstrip()
        if cmd[0] == "I":
            heapq.heappush(minHeap,(int(cmd[2:]),id))
            heapq.heappush(maxHeap,(-int(cmd[2:]),int(cmd[2:]),id))
            visited[id] = True 
            id += 1
        else:
            if cmd[2:] == '-1':
                while minHeap and not visited[minHeap[0][1]]:
                    heapq.heappop(minHeap)
                if minHeap:
                    visited[minHeap[0][1]] = False
                    heapq.heappop(minHeap)
            else:
                while maxHeap and not visited[maxHeap[0][2]]:
                    heapq.heappop(maxHeap)
                if maxHeap:
                    visited[maxHeap[0][2]] = False
                    heapq.heappop(maxHeap)
            id += 1

    while minHeap and not visited[minHeap[0][1]]:
        heapq.heappop(minHeap)
    while maxHeap and not visited[maxHeap[0][2]]:
        heapq.heappop(maxHeap)
    if len(minHeap) == 0 or len(maxHeap) == 0:
        print("EMPTY")
    else:
        print(maxHeap[0][1],minHeap[0][0])