[백준] 7662번 - 이중 우선순위 큐 (파이썬)

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

 

# 이중 우선순위 큐
import heapq

T = int(input())
for _ in range(T):
    N = int(input())
    min_heap = []
    max_heap = []
    visited = [False] * N
    for idx in range(N):
        order, data = input().split()
        data = int(data)
        if order == 'I':
            heapq.heappush(min_heap, (data, idx))
            heapq.heappush(max_heap, (-data, idx))
            visited[idx] = True
        elif order == 'D':
            if data == 1:
                while max_heap and not visited[max_heap[0][1]]:
                    heapq.heappop(max_heap)
                if max_heap:
                    data, idx = heapq.heappop(max_heap)
                    visited[idx] = False
            elif data == -1:
                while min_heap and not visited[min_heap[0][1]]:
                    heapq.heappop(min_heap)
                if min_heap:
                    data, idx = heapq.heappop(min_heap)
                    visited[idx] = False

    while min_heap and not visited[min_heap[0][1]]:
        heapq.heappop(min_heap)
    while max_heap and not visited[max_heap[0][1]]:
        heapq.heappop(max_heap)

    if max_heap and min_heap:
        print(-max_heap[0][0], min_heap[0][0])
    else:
        print('EMPTY')

 

자료구조, 힙
테스트 케이스만큼 반복
1. 최소 힙과 최대 힙을 정의, 방문 여부 리스트 정의
2. 'I'일 경우 양쪽 힙에 모두 push, visited를 True로 설정
3. 'D'일 경우
    - pop된 값들 (visited가 False인 값들)을 모두 pop해준다.
    - 1이고 max_heap이 빈 상태가 아니면, 최댓값 pop
    - -1이고 min_heap이 빈 상태가 아니면 최솟값 pop
    - pop한 인덱스의 visited를 False로 설정
4. pop된 값들 (visited가 False인 값들)을 모두 pop 해주기
5. 비어있다면 EMPTY 출력, 아니면 최댓값, 최솟값 출력

 

하나의 정보를 두 가지 자료구조(최대 힙, 최소 힙)로 관리를 하는 문제

힙은 인덱스 0을 제외하고서는 보장이 되지 않기 때문에 visited로 pop여부를 관리한다.