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

✔ 풀이를 위한 아이디어

• 우선순위 큐 (Priority Queue)와 힙 (Heap)의 응용
  
  

✔ 수정 전 코드

import sys
import heapq

T = int(sys.stdin.readline())

for _ in range(T):
    max_Heap = []
    min_Heap = []
    count = 0
    k = int(sys.stdin.readline())
    for _ in range(k):
        cmd, num = sys.stdin.readline().strip().split()
        if cmd == 'I':
            heapq.heappush(max_Heap, (-int(num), int(num)))
            heapq.heappush(min_Heap, int(num))
            count += 1
        elif cmd == 'D' and count > 0:
            if int(num) == 1:
                heapq.heappop(max_Heap)
            else:
                heapq.heappop(min_Heap)
            count -= 1
    if count > 0:
        print(heapq.heappop(max_Heap)[1], heapq.heappop(min_Heap))
    else:
        print("EMPTY")

• 처음 내 아이디어는 어설프지만 위의 그림과 같았다.
• Max Heap과 Min Heap에서 핵심적인 요소는 결국 index 0에 있는 최댓값과 최솟값이다. 따라서 두개의 Heap을 관리하되, 최댓값이 필요 할 때는 Max Heap에서 Pop 해주고, 최솟값이 필요하면 Min Heap에서 Pop 해주는 것이다.
• count라는 변수를 두어서 위의 그림처럼 교차되는 일만 방지한다면, 결국 화살표는 점차점차 가까워지면서 최댓값과 최솟값을 잘 출력할 것으로 예상되었다. (최댓값과 최솟값은 숫자를 순서대로 배열했을 때 끝 지점에 존재하기 때문에)
• 하지만 문제는, count가 0이 되었다가 다시 새로운 값이 Push 될 때 일어난다.

• 위의 그림처럼 count가 0이 되고 난 후, Min Heap에는 4, 5가 들어있고 Max Heap에는 3, 2가 들어있는 상황을 가정해보자.
• 이때 6이라는 요소가 들어오게 되면, Max Heap에서는 문제가 일어나지 않지만, Min Heap에서 최솟값은 4가 되는데 이는 잘못되었다.
• 사실 4와 5라는 값은 이미 Max Heap에서 삭제한 값이기 때문에 Min Heap에는 값이 6만 남아있어야 하며, 최솟값 역시 6이어야 하기 때문이다.

✔ 수정 후 코드

import sys
import heapq

T = int(sys.stdin.readline())

for _ in range(T):
    max_Heap = []
    min_Heap = []
    k = int(sys.stdin.readline())
    visited = [False]*k
    for i in range(k):
        cmd, num = sys.stdin.readline().strip().split()
        if cmd == 'I':
            heapq.heappush(max_Heap, (-int(num), i))
            heapq.heappush(min_Heap, (int(num), i))
            visited[i] = True
        elif cmd == 'D':
            if int(num) == 1:
                while max_Heap and not visited[max_Heap[0][1]]:
                    heapq.heappop(max_Heap)
                if max_Heap:
                    visited[max_Heap[0][1]] = False
                    heapq.heappop(max_Heap)
            else:
                while min_Heap and not visited[min_Heap[0][1]]:
                    heapq.heappop(min_Heap)
                if min_Heap:
                    visited[min_Heap[0][1]] = False
                    heapq.heappop(min_Heap)
    while max_Heap and not visited[max_Heap[0][1]]:
        heapq.heappop(max_Heap)
    while min_Heap and not visited[min_Heap[0][1]]:
        heapq.heappop(min_Heap)

    if max_Heap and min_Heap:
        print(-max_Heap[0][0], min_Heap[0][0])
    else:
        print("EMPTY")

• 위의 이유로 인해, count 대신 visited라는 배열을 사용하여 이미 다른 Heap에서 뽑혀나간 요소인지 확인하도록 하였다. (뽑혀나간 요소를 구분하지 못해서 틀렸었기 때문이다.)
• Push 해줄 때 해당 index의 visited 값을 True로 바꿔줌으로써 존재한다는 것을 표시하고, Pop 해줄 때 False로 바꿔줌으로써 뽑혀나간 요소라는 것을 표시하였다. 이 때 넣는 숫자를 key 값으로 쓴 것이 아닌, i 값을 key 값으로 쓴 이유는 같은 숫자가 여러 개 존재할 수 있기 때문이다.
• Pop 할 때 visited 값이 False인 요소는 무시하고 버려버리는 처리를 꼭 해주어야 했다.
  
  

• 수정 전 코드로 인해서 1차적으로 틀렸었고, 수정 후 코드에서 급하게 제출하다가 visited 값이 아닌 다른 값에 True를 넣어주는 실수를 하는 바람에 런타임 에러가 났었다.

✔ 관련 개념

• 힙 (Heap)과 heapq 모듈 활용 ++