문제풀이/BOJ
[Python] BOJ/백준 7662번 이중 우선순위 큐
서채리
2022. 6. 24. 23:46
[문제]
https://www.acmicpc.net/problem/7662
[풀이]
가장 간단한 방법인 max, min 으로 찾는 방법은 시간초과가 나온다 (당연함)
파이썬의 우선순위 큐 문제는 heapq, PriorityQueue 두 가지 라이브러리를 사용할 수 있다.
요약하면 PriorityQueue 는 스레드를 Thread-safe를 위해 확인 절차를 걸쳐 오버헤드가 있고 heapq는 Non-safe 하기 때문에 PriorityQueue 보다 더 빠르다고 한다.
→ 그래서 heapq 라이브러리를 사용하였다.
'힙(heap)'이란?
- 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조
- 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조
- 일종의 반정렬 상태(느슨한 정렬 상태) 유지
- 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도
- 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리
- 힙 트리에서는 중복된 값 허용 (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)
이 문제의 중요한 점은 아래 두가지라고 생각한다.
- 파이썬의 heapq는 최소힙만 지원하기 때문에 최대힙은 따로 구현해주어야 한다.
- 최대힙 구현을 위해 삽입 시 입력받은 n 에 -1을 곱하고 결과값을 출력 시에는 -1을 다시 곱한 후 출력
- 최대힙, 최소힙을 동기화 시켜주어야 한다.
- 힙에 push 할 때 입력받은 값 n 과 반복문이 몇 번 수행되었는지 가리키는 변수 i 를 튜플 형태로 함께 넣어줌
(파이썬의 튜플 비교연산은 첫 번째 원소를 기준으로 판단하기 때문에 힙의 구동에 영향 X) - 삭제 연산 시 id를 기준으로 해당 노드가 다른 힙에서 삭제된 노드인지 확인하기 위해 visited 플래그 리스트 사용
- 이미 삭제된 노드인 경우 삭제되지 않은 노드가 나올 때까지 모두 버림
- 삭제 대상 노드 등장 시 삭제
- 모든 연산이 끝난 후에도 남아있는 동기화 되지 않은 노드가 있을 수 있기 때문에 각 힙의 false로 되어있는 값들은 버려주어 동기화 시킴
- 힙에 push 할 때 입력받은 값 n 과 반복문이 몇 번 수행되었는지 가리키는 변수 i 를 튜플 형태로 함께 넣어줌
[코드]
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")