[BOJ] 1655 - 가운데를 말해요(Python)- 우선순위 큐(최대힙, 최소힙)

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

우선순위 큐(Priority Queue)

• 들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나오는 구조
• 우선순위를 따로 지정하지 않으면 값이 작을 수록 우선순위가 높다
• 힙을 통해 구현 -> heapq 모듈을 통해 구현할 수 있음
• 즉 완전이진트리 구조를 가지는 데, 대표적으로 최대힙, 최소힙
• 배열이나 연결리스트는 왜 X? -> 시간 복잡도 O(n)

최대힙

루트 노드가 가장 큰 값을 가지며, 부모노드는 자식노드보다 항상 큰 값

최소힙

루트 노드가 가장 작은 값, 부모노드는 자식노드 보다 항상 작은 값

파이썬에서 힙 구현하는 세가지 방법
1) 직접 구현
2) heapq 모듈
3) PriorityQueue 모듈

import heapq

nums = [5, 1, 2, 10, 8]
heap = []
for num in nums:
    # heap 삽입 - heapq.heappush(힙이름, 데이터)
    # 우선순위를 주고 싶으면 데이터 부분에 (우선순위, 데이터)의 튜플로 삽입하면 됨
    heapq.heappush(heap, n)
while heap:
    # heap 삭제 - heapq.heappop(힙이름)
    # 우선순위가 높은 순서대로 즉 데이터가 낮은 순서대로 삭제 됨. (heapq는 기본적으로 최소힙이라서)
    # (우선순위, 데이터) 튜플 구조를 가지는 힙의 경우
    heappop(힙이름)[1]로 데이터 가져올 수 있음
    print(heapq.heappop(heap))
    # 1 2 8 5 10

최대힙

nums = [5, 1, 2, 10, 8]
heap = []
for num in nums:
    # 작을수록 우선순위 높으므로 마이너스를 붙여 반대로
    heapq.heappush(heap, (-n, n))
while heap:
    print(heapq.heappop(heap)[1])
    # 10 8 5 2 1

PriorityQueue 사용

from queue import PriorityQueue
Q = PriorityQueue()
# 원소 삽입
Q.put(데이터)
Q.put((우선순위, 데이터))
# 원소 삭제 - 우선순위 높은 순서대로 삭제
Q.get() 
Q.get()[1]

"가운데를 말해요"

https://www.acmicpc.net/problem/1655
1. 백준이가 정수 외칠 때마다 지금가지 나온 수의 중간 값 말해야 됨
2. 짝수개 외쳤으면 중간 두 수중 작은 수 말해야 됨
3. 빠듯한 시간 제한

--> 우선순위 큐로 구현
--> 왼쪽 최대 힙, 오른쪽 최소 힙을 통해 원소의 개수를 비교해가며 중간 값 업데이트

# 1655 가운데를 말해요 - 우선순위 큐 골드 2 김수민
import heapq
import sys
left_h = [] # 왼쪽 최대 힙
right_h = [] # 오른쪽 최대 힙
mid = 0
N = int(sys.stdin.readline())
mid = int(sys.stdin.readline())
print(mid)
for i in range(1, N):
    n = int(sys.stdin.readline())
    if n > mid: # 중간 값보다 크면
        heapq.heappush(right_h, n) # 오른쪽 큐에 삽입
        if len(left_h) + 1 < len(right_h): # 오른쪽 큐가 원소 2개이상 더 많으면
            heapq.heappush(left_h, (-mid, mid)) # 최소 값 업데이트
            mid = heapq.heappop(right_h)
    else: # 중간 값보다 작으면
        heapq.heappush(left_h, (-n, n)) # 왼쪽 큐에 삽입
        if len(right_h) < len(left_h): # 왼쪽 큐가 원소 1개 이상 더 많으면(중간값 2개일 때 더 작은 값이 mid이므로)
            heapq.heappush(right_h, mid) # 중간 값 업데이트
            mid = heapq.heappop(left_h)[1]
    print(mid)