백준 이중 우선순위 큐 - 7662

문제 링크

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

7662번: 이중 우선순위 큐

문제 설명

문제 풀이 과정

• 우선 입력부를 처리하고, 조건에 따라 분기한다.
• 생각해보니 정렬을 minheap으로 하면 간단할 것 같아서 라이브러리 가져와 해결
  • 틀림 min heap의 최대값을 구하는 과정에서 max함수를 사용하여 시간초과 문제를 발견함 max heap도 만들어서 처리하는 방식을쓰면 logn + logn이 될 듯함.
  • 근데 결국에 max값을 max heap에서 빼도 min heap에서도 뺴줘야함
  • 그러면 min heap만 사용하고 max값 찾아서 빼는거랑 뭐가 다르지?
  • visited를 사용하여 해결한 풀이를 봤고 같은 방식으로 해결함

풀이 코드

import sys
from heapq import heappush , heappop
T = int(sys.stdin.readline())
for i in range(T):
    minheap ,maxheap = [], []
    visited = [False] * 1000001 
    K = int(sys.stdin.readline())
    lst = [sys.stdin.readline().split() for j in range(K)]

    for key in range(len(lst)):
        op = lst[key]
        if op[0] == 'I':
            heappush(minheap,(int(op[1]),key)) # min heap으로 저장
            heappush(maxheap, (-int(op[1]),key)) # max heap으로 저장
            visited[key] =  True
        else:
            if op[1] == '-1':
                while minheap and not visited[minheap[0][1]]:
                    heappop(minheap)
                if minheap:
                    visited[minheap[0][1]] = False
                    heappop(minheap)
            else:
                while maxheap and not visited[maxheap[0][1]]:
                    heappop(maxheap)
                if maxheap:
                    visited[maxheap[0][1]] = False
                    heappop(maxheap)
    while minheap and not visited[minheap[0][1]]:
        heappop(minheap)
    while maxheap and not visited[maxheap[0][1]]:
        heappop(maxheap)

    try:
        print(-maxheap[0][0], minheap[0][0])
    except IndexError:
        print('EMPTY')