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

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

7662번: 이중 우선순위 큐

문제는 간단하게 데이터를 삽입하고 최대값, 최소값을 삭제 해주면서 데이터를 관리하는 작업이였다.

 

list를 선언하고 list.index, list.remove 등 list 연산을 쓰면 무조껀 시간초과가 나기때문에

최소힙, 최대힙을 사용하여 최소, 최댓값에 대한 처리를 해야겠다고 생각했다.

 

여기서 유의할점은 단순히 우선순위큐 모듈인 PriorityQueue()을 사용하려고 했지만 최소, 최대를 모두 고려해줘야 하기 때문에 최소힙, 최대힙 2개의 힙을 구현한다음 최소힙에서 빼준 값을 최대힙에서도 빼줘야하기 때문에 tuple 형태로 idx값을 같이 저장해서 한쪽힙에서 삭제 연산이 일어났으면 visited 방문처리를 해줘서 나머지 힙에서도 처리를 하게했다.

 

import heapq
import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    k = int(input())
    max_heapq = []
    min_heapq = []
    visited = [0] * k
    for i in range(k):
        command, num = input().split()

        if command == 'I':
            heapq.heappush(min_heapq,(int(num),i))
            heapq.heappush(max_heapq,(-1 * int(num),i))
        else:
            if num == '1':
                while max_heapq:
                    if visited[max_heapq[0][1]] == 1:
                        heapq.heappop(max_heapq)
                    else:
                        break
                if max_heapq:
                    visited[max_heapq[0][1]] = 1
                    heapq.heappop(max_heapq)

            elif num == '-1':
                while min_heapq:
                    if visited[min_heapq[0][1]] == 1:
                        heapq.heappop(min_heapq)
                    else:
                        break
                if min_heapq:
                    visited[min_heapq[0][1]] = 1
                    heapq.heappop(min_heapq)

    while max_heapq:
            if visited[max_heapq[0][1]] == 1:
                heapq.heappop(max_heapq)
            else:
                break
    while min_heapq:
            if visited[min_heapq[0][1]] == 1:
                heapq.heappop(min_heapq)
            else:
                break

    if min_heapq and max_heapq:
        print(-max_heapq[0][0], min_heapq[0][0])
    else:
        print('EMPTY')