[백준] 7662번 : 이중우선순위 큐

7662번: 이중 우선순위 큐

처음 이 문제를 풀때 이분탐색법으로 문제를 해결하려고 했으나 시간 초과 판정을 받았습니다.

큐를 하나두고 이분탐색으로 큐를 삽입할 인덱스를 결정하여 해당 인덱스에 값을 삽입한다면

큐의 첫번째 원소값은 최소값 큐의 마지막 원소는 최대값을 갖게 됩니다.

T = int(input())
for _ in range(T):
    k = int(input())
    queue = deque()
    
    for _ in range(k):
        cmd , num = map(str, input().split())
        number = int(num)
        if cmd == 'I': # 삽입
            if queue:
                if number > queue[-1]:
                    queue.append(number)
                else:
                    idx = bisect_left(queue, number)
                    queue.insert(idx, number)
            else:
                queue.append(number)
        else:# 삭제
            if queue:
                if number == 1: # 우선순위가 높은 값을 지운다.(숫자가크다)
                    queue.pop()
                else: # 우선순위가 낮은 값을 지운다. (숫자가작다)
                    queue.popleft()
    if queue:
        print(queue[-1], end=' ')
        print(queue[0])
    else:
        print("EMPTY")

하지만 해당문제는 시간초과 판정을 받았습니다. 결국에는 해당문제는 우선순위큐 2개로 문제를 해결해야만 했습니다.

듀얼 우선순위 큐 문제로 해결 할 수 있습니다.

최대힙큐와 최소힙큐를 두어서 각각의 우선순위 큐의 배열의 첫번째 인덱스의 값을

1. 최대 힙큐 : 최대값
2. 최소 힙큐 : 최소값

위의 조건이 맞도록 구성해야한다.

import heapq

T = int(input())
for _ in range(T):
    k = int(input())
    minq = []
    maxq = []
    visited = [False] * k
    for i in range(k):
        op , temp = map(str, input().split())
        number = int(temp)
        if op == "I":
            heapq.heappush(minq, [number, i])
            heapq.heappush(maxq, [-number, i])
            visited[i] = True
        else:
            if number == 1: # 큰값을 제거하라
                while maxq and not visited[maxq[0][1]]:
                    heapq.heappop(maxq)
                    
                if maxq:
                    visited[maxq[0][1]] = False
                    heapq.heappop(maxq)
            else:
                while minq and not visited[minq[0][1]]:
                    heapq.heappop(minq)
                    
                if minq:
                    visited[minq[0][1]] = False
                    heapq.heappop(minq)
                    
    while minq and not visited[minq[0][1]]:
        heapq.heappop(minq)
        
    while maxq and not visited[maxq[0][1]]:
        heapq.heappop(maxq)
        
    if minq and maxq:
        print(-maxq[0][0], minq[0][0])
    else:
        print("EMPTY")