#108 백준 파이썬 [1655] 가운데를 말해요 - 힙, 우선순위 큐

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

 



#Solution

처음엔 우선순위큐를 위해 힙정렬로 했다가 시간초과가 나서, 힙을 두개로 쪼갰다. 중앙값은 결국 수를 동등하게 나누어서 하위 1/2 수 중 가장 큰 수, 상위 1/2 중 가장 작은 수이다. 따라서 최대 힙, 최소 힙 두가지를 만들어서 풀어주면 된다.

 

1) 힙정렬 (시간 초과)

import sys
import heapq

numbers = int(input())
heap = []

for _ in range(numbers):
    num = int(input())
    heapq.heappush(heap, num)
    temp_heap = list(heap)
    for _ in range((len(temp_heap)+1)//2 - 1):
        heapq.heappop(temp_heap)
    print(temp_heap[0])

 

2) 최대 최소힙 (pypy3로 언어 바꾸어 풀어야함)

import sys
import heapq

numbers = int(input())
max_heap = []
min_heap = []

for _ in range(numbers):
    num = int(input())
    if len(max_heap) == len(min_heap):
        heapq.heappush(max_heap, (-num, num))
    else:
        heapq.heappush(min_heap, (num, num))
    
    if min_heap and max_heap[0][1] > min_heap[0][1]:
        temp_max = heapq.heappop(max_heap)[1]
        temp_min = heapq.heappop(min_heap)[1]
        heapq.heappush(max_heap, (-temp_min, temp_min))
        heapq.heappush(min_heap, (temp_max, temp_max))
    print(max_heap[0][1])