1655: 가운데를 말해요 (Python)

<문제 유형>: 우선순위 큐, 힙 

큐(Queue)

  : FIFO(First In First Out)의 자료구조로 먼저 들어온 데이터가 먼저 추출되는 구조를 갖는다. 

 

우선순위 큐(Priority Queue)

  : 각 자료에 부여된 우선순위에 따라서 추출되는 순서가 정해지는 자료 구조이다. 

 

힙(Heap)

  : 우선순위 큐의 구현을 위한 완전 이진트리의 자료구조, 파이썬에서는 최소힙이 제공된다. 

   또한, 이진트리의 힙 구조를 이용하면 최솟값과 최댓값을 구하는 데에 걸리는 시간이 단순 배열보다 매우 빠르다는 장점이 있다. (단순 배열의 시간복잡도 O(n), 힙을 이용한 탐색 시간복잡도 O(log₂n) )

  : 최대힙 (Max Heap) - 부모 노드가 항상 자식 노드보다 큰 구조, 루트 노드에 최댓값이 저장됨

  : 최소힙 (Min Heap) - 부모 노드가 항상 자식 노드보다 작은 구조, 루트 노드에 최솟값이 저장됨 

 

 : 파이썬 라이브러리 heapq을 이용한 최대힙, 최소힙 구현

  heapq 라이브러리는 최소힙을 지원하므로 최대힙을 구현하기 위해서는 힙 원소에 (-num, num)으로 추가해 첫원소를 기준으로 배열되는 특징을 이용한다. 

   - 최대힙: heapq.heappush( lst, ( -num, num) )

   - 최소힙: heapq.heappush( lst, (num, num) )

  : 파이썬 라이브러리 heapq을 이용한 힙 원소 추출 

   -  heapq.heappop(lst) : 루트노드의 원소를 리턴하며 트리에서 추출한다

 

 

<구현해야 하는 것>

- 우선순위 큐 구조를 이용한 중간값 출력

- left_heap: 중갑값 이하의 최대힙 

  right_heap: 중간값 이상의 최소힙 

- 각 원소를 추가할 때마다 left_heap, right_heap 의 갯수가 같으면 left 에, 그렇지 않으면 right heap에 저장해 원소 추가 후 left_heap의 루트 원소와 right_heap의 루트 원소를 비교해 left_heap 의 최댓값이 right_heap의 최솟값보다 작거나 같게 유지한다. 

 

(※ 리스트 구조를 이용해 중간값을 매번 따지면 시간초과가 나므로 반드시 힙 구조를 이용한다)

---

import sys 
import heapq # 최소힙 구현 
input = sys.stdin.readline 
n = int(input())

left_heap = [] # 최대힙 
right_heap = [] # 최소힙 
reply = [] 

for i in range(n):
    num = int(input())

    # 큐에 추가 
    if len(left_heap) == len(right_heap):
        heapq.heappush(left_heap, (-num, num))
    else: 
        heapq.heappush(right_heap, (num, num))
    
    # left_heap의 루트노트가 right_heap의 루트노드보다 작도록 유지 
    if right_heap and left_heap[0][1] > right_heap[0][1]:
        small = heapq.heappop(right_heap)[1]
        big = heapq.heappop(left_heap)[1]
        heapq.heappush(left_heap, (-small, small))
        heapq.heappush(right_heap, (big, big))

    reply.append(left_heap[0][1])

for i in reply:
    print(i)