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

문제

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

풀이

• 이중 우선순위 큐에 저장된 데이터 중, 최댓값과 최솟값 출력
• 이중 우선순위 큐란? 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조
  • 차이점: 데이터를 삭제할 때 연산 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제

문제에 주어진 큐에 저장된 값 자체가 우선순위라고 간주합니다.
즉 D 1 명령이 주어지면 가장 큰 값(우선순위)이 제거가 되고 D -1 명령이 주어지면 가장 작은 값이 제거가 됩니다.

최소 힙과 최대 힙을 활용하여 풀어보겠습니다.
파이썬에서는 최대 힙의 구현이 되지 않기 때문에 음수를 넣어 최대 힙을 구현해 풀었습니다.

각 연산 별로 i번째 값들이 살아있는지 여부를 판별하기 위해 visited를 선언해 줍니다.

t = int(input())
for tc in range(t):
    k = int(input())
    min_q, max_q = [], [] # 최소힙, 최대힙
    visited = [False] * k # 방문 여부

k만큼 반복하여 명령어와 값을 입력 받습니다.

    for i in range(k):
        cmd, val = input().split()
        val = int(val)

I일 경우 최소힙과 최대힙에 값을 추가하는데, 인덱스 값도 같이 넣어 줍니다.
아직 힙 안에 값이 존재하는지 판별할 수 있게 visited[i]를 True로 선언

        if cmd == 'I':
            heapq.heappush(min_q, (val, i)) # 최소힙 값 입력
            heapq.heappush(max_q, (-val, i)) # 최대힙 값 입력
            visited[i] = True

D일 경우는 최솟값 삭제, 최댓값 삭제 2가지를 구현해야 합니다.
최댓값 삭제부터 구현해 보겠습니다.

값을 삭제하기 전에 가장 앞에 존재하는 값 즉, 최댓값이 존재하는 값일 경우에 삭제를 해야 하므로 visited에서 True일 경우에 값을 삭제 처리를 해야 합니다.
때문에 while문을 통해 visited값이 False인 경우 그 값들은 모두 삭제를 해줍니다.

유효한 값이 나오게 된다면, 실제로 삭제를 수행해줍니다.
visited = False, heapq.heappop(max_q)

        elif cmd == 'D':
            if val == 1:
                while max_q and not visited[max_q[0][1]]:
                    heapq.heappop(max_q)
                
                if max_q:
                    visited[max_q[0][1]] = False
                    heapq.heappop(max_q)
            

위와 동일한 방식으로 최솟값도 처리를 해줍니다.

            elif val == -1:
                while min_q and not visited[min_q[0][1]]:
                    heapq.heappop(min_q)
                
                if min_q:
                    visited[min_q[0][1]] = False
                    heapq.heappop(min_q)
    

모든 연산이 끝난 후에도 힙에 이미 삭제된 값이 남아 있을 수 있으므로, 마지막에 한 번 더 유효한 값인지 체크를 합니다.

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

마지막으로 최대힙과 최소힙에 값이 존재할 때, 최댓값과 최솟값을 출력하고
값이 존재하지 않으면 EMPTY를 출력하면 끝

    if max_q and min_q:
        print(-max_q[0][0], min_q[0][0])
    else:
        print("EMPTY")

코드

import heapq, sys
input = sys.stdin.readline

t = int(input())
for tc in range(t):
    k = int(input())
    min_q, max_q = [], []
    visited = [False] * k
    
    for i in range(k):
        cmd, val = input().split()
        val = int(val)
        
        if cmd == 'I':
            heapq.heappush(min_q, (val, i))
            heapq.heappush(max_q, (-val, i))
            visited[i] = True
        
        elif cmd == 'D':
            if val == 1:
                while max_q and not visited[max_q[0][1]]:
                    heapq.heappop(max_q)
                
                if max_q:
                    visited[max_q[0][1]] = False
                    heapq.heappop(max_q)
            
            elif val == -1:
                while min_q and not visited[min_q[0][1]]:
                    heapq.heappop(min_q)
                
                if min_q:
                    visited[min_q[0][1]] = False
                    heapq.heappop(min_q)
    
    while max_q and not visited[max_q[0][1]]:
        heapq.heappop(max_q)
    while min_q and not visited[min_q[0][1]]:
        heapq.heappop(min_q)
    
    if max_q and min_q:
        print(-max_q[0][0], min_q[0][0])
    else:
        print("EMPTY")