7662 이중 우선순위 큐

골5

multi set과 map을 잘 다룬다면 쉽게 풀리는 문제이지만

난 그런걸 잘 몰라서 queue 를 통해서 구현했다.

queue를 통해서 구현하면 난이도가 치솟는다.

우선 우선순위 큐를 구현하기 위해서는 heap 자료구조를 거의 무조건 사용해야 하니, heap을 이용해서 구현하려고 했다.

그리고 heap을 max_heap, min_heap 을 두 개 사용해서 구현할지 아니면 한 개의 heap만으로 max, min 을 계속 재정렬하면서 사용할지 고민했다.

전자의 경우 복잡하지만 시간적으로는 안정적일것 같았고, 후자는 매우 간단하게 구현할 수 있지만 시간복잡도에서 물음표 였다.
왠지 heap의 정렬 O(logn) 이라는 시간이 나에게 뭔가 마법봉같이 이 문제를 해결해줄것이라 믿었던 것 같다.

일단 구현 하니까 테스트 돌기도 전에 시간초과가 나왔다.

구현은 max 삭제의 경우 힙을 max로 재정렬, min 삭제의 경우 min으로 재정렬 하면서 삭제를 해준다. 뭐..당연히 시간초과

때문에 heap을 두 개로 만들어서 구현을 해준다.

여기서 문제는 두 개의 힙에서 각자 값을 삭제해주기 때문에 두 힙을 동기화시켜주는 과정이 반드시 필요하다는 것이다.

이 동기화를 위해서는 양쪽에 삽입되는 모든 원소에 대해서 삭제되었는지 확인해주는 배열이 필요하다. 이 배열을 visited로 만들어주고 삽입될때 해당 원소에 대해 true 처리를 하고 min_heap이나 max_heap에서 삭제될 경우 False로 만들어준다.

이렇게 하고 특정 삭제가 일어날때마다 while 문을 돌면서 false로 된 원소들은 다른 힙에서 이미 삭제된 원소이므로 모두 삭제해준다.

import heapq, sys
read = sys.stdin.readline
T = int(read())

def solution(order, num, i):
    if order == "I":
        heapq.heappush(heap_min, [num, i])
        heapq.heappush(heap_max, [-num, i])
        visited[i] = True

    elif order == "D":
        if not heap_max or not heap_min:
            return

        if num == -1: # 최소값 삭제
            while heap_min and not visited[heap_min[0][1]]:
                heapq.heappop(heap_min)

            if heap_min:
                visited[heap_min[0][1]] = False
                heapq.heappop(heap_min)
        elif num == 1:
            while heap_max and not visited[heap_max[0][1]]:
                heapq.heappop(heap_max)

            if heap_max:
                visited[heap_max[0][1]] = False
                heapq.heappop(heap_max)

for _ in range(T):
    k = int(read())
    visited = [False] * 1000001
    heap_max, heap_min = [], []

    for i in range(k):
        order, num = read().split(" ")
        solution(order, int(num), i)

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

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

    if heap_max and heap_min:
        print(-heap_max[0][0], heap_min[0][0])

    else:
        print("EMPTY")