[Python] BOJ/백준 7662번 이중 우선순위 큐

[문제]

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

7662번: 이중 우선순위 큐

 

 

[풀이]

가장 간단한 방법인 max, min 으로 찾는 방법은 시간초과가 나온다 (당연함)

 

파이썬의 우선순위 큐 문제는 heapq, PriorityQueue 두 가지 라이브러리를 사용할 수 있다.

https://stackoverflow.com/questions/36991716/whats-the-difference-between-heapq-and-priorityqueue-in-python?answertab=trending#tab-top

What's the difference between heapq and PriorityQueue in python?

요약하면 PriorityQueue 는 스레드를 Thread-safe를 위해 확인 절차를 걸쳐 오버헤드가 있고 heapq는 Non-safe 하기 때문에 PriorityQueue 보다 더 빠르다고 한다.

→ 그래서 heapq 라이브러리를 사용하였다.

 

'힙(heap)'이란?

• 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조
• 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조
• 일종의 반정렬 상태(느슨한 정렬 상태) 유지
  • 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도
  • 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리
• 힙 트리에서는 중복된 값 허용 (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)

---

이 문제의 중요한 점은 아래 두가지라고 생각한다.

1. 파이썬의 heapq는 최소힙만 지원하기 때문에 최대힙은 따로 구현해주어야 한다.
   • 최대힙 구현을 위해 삽입 시 입력받은 n 에 -1을 곱하고 결과값을 출력 시에는 -1을 다시 곱한 후 출력
2. 최대힙, 최소힙을 동기화 시켜주어야 한다.
   • 힙에 push 할 때 입력받은 값 n 과 반복문이 몇 번 수행되었는지 가리키는 변수 i 를 튜플 형태로 함께 넣어줌
     (파이썬의 튜플 비교연산은 첫 번째 원소를 기준으로 판단하기 때문에 힙의 구동에 영향 X)
   • 삭제 연산 시 id를 기준으로 해당 노드가 다른 힙에서 삭제된 노드인지 확인하기 위해 visited 플래그 리스트 사용
     • 이미 삭제된 노드인 경우 삭제되지 않은 노드가 나올 때까지 모두 버림
     • 삭제 대상 노드 등장 시 삭제
   • 모든 연산이 끝난 후에도 남아있는 동기화 되지 않은 노드가 있을 수 있기 때문에 각 힙의 false로 되어있는 값들은 버려주어 동기화 시킴

 

 

[코드]

import sys
import heapq

for T in range(int(sys.stdin.readline())):
    k = int(sys.stdin.readline())
    visited = [False] * k
    maxH, minH = [], []
    for i in range(k):
        operation, n = sys.stdin.readline().split()
        n = int(n)

        if operation == 'I':
            heapq.heappush(minH, (n, i))
            heapq.heappush(maxH, (-n, i))
            visited[i] = True
        elif n == 1:
            while maxH and not visited[maxH[0][1]]:
                heapq.heappop(maxH)
            if maxH:
                visited[maxH[0][1]] = False
                heapq.heappop(maxH)
        else:
            while minH and not visited[minH[0][1]]:
                heapq.heappop(minH)
            if minH:
                visited[minH[0][1]] = False
                heapq.heappop(minH)
    while minH and not visited[minH[0][1]]:
        heapq.heappop(minH)
    while maxH and not visited[maxH[0][1]]:
        heapq.heappop(maxH)
    print(-maxH[0][0], minH[0][0]) if maxH and minH else print("EMPTY")