[백준] 7663번 이중 우선순위 큐 - python 파이썬

문제

 

 

일단 이 문제를 보면 연산 횟수인 k의 범위가 100만 이하로 굉장히 크다.

그렇기 때문에 연산을 할때마다 정렬을 한다면 무조건 시간초과 가 발생한다는 것을 알 수 있다.

 

 

시간복잡도를 최대한 낮게 하면서 최댓값 또는 최솟값을 구하는 알고리즘을 생각하면 heap 이 딱 떠오르게 된다.

 

근데 문제는 최댓값 최솟값을 동시에 구해줘야한다는 것이다

 

최대힙, 최소힙 둘 다 구현하면 되는거 아닌가?  할 수도 있지만

 

최댓값 또는 최솟값을 삭제할 때 서로 어떻게 반영할 지가 이 문제의 관건이다.

 

 

이는 heap에 추가 할 때 몇번째  연산인지 정보가 담긴 key 값(몇 번째 연산이 되는지에 대한 정보는 고유하기 때문에 key 값으로 설정해주었다.)을 같이 저장해두어 방문여부를 통해 체크 해주면 된다

 

 

 

visit[key] = True -> 해당 숫자는 Insert되었고 삭제된 적 없다는 뜻
visit[key] = False -> 해당 숫자는 Insert된적 없거나 삭제되었다는 뜻

 

visit 배열의 범위는 k의 범위로 해주면 된다 .

 

정답 코드

 

import sys
import heapq

input = sys.stdin.readline
t = int(input())

for _ in range(t):
    visit = [False] * 1_000_001
    max_heap, min_heap= [],[]

    k = int(input())

    for key in range(k):
        order = input().rsplit()

        if order[0] == 'I':
            heapq.heappush(max_heap,(int(order[1])*-1,key))
            heapq.heappush(min_heap, (int(order[1]),key))
            visit[key] = True

        elif order[0] == 'D':
            if order[1] == '1':
                #삭제 반영 안된 것들 체크
                while max_heap and not visit[max_heap[0][1]]:
                        heapq.heappop(max_heap)
                if max_heap:
                    visit[max_heap[0][1]] = False
                    heapq.heappop(max_heap)
            elif order[1] == '-1':
                #삭제 반영 안된 것들 체크
                while min_heap and not visit[min_heap[0][1]]:
                        heapq.heappop(min_heap)
                if min_heap:
                    visit[min_heap[0][1]] = False
                    heapq.heappop(min_heap)
    #삭제 반영 안된 것들 마지막으로 체크
    while min_heap and not visit[min_heap[0][1]]:
        heapq.heappop(min_heap)
    while max_heap and not visit[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")