|
import sys
input = sys.stdin.readline
import heapq
under = []
over = []
n = int(input())
for i in range(n) :
x = int(input())
if len(under) == len(over) :
heapq.heappush(under, -x)
else :
heapq.heappush(over, x)
if over != [] and -under[0] > over[0] :
a = -heapq.heappop(under)
b = heapq.heappop(over)
heapq.heappush(under, -b)
heapq.heappush(over, a)
print(-under[0])
|
heap의 구현은 이전 문제에서 해봤으니 생략하고 heapq를 import했다.
힙을 2개나 쓰는데 이걸 하나하나 구현하긴 좀...
최소 힙 over, 그리고 최소 힙 under에 부호를 뒤집어 넣어 최대 힙으로 이용하여 2개의 힙을 쓴다.
under와 over에 원소를 번갈아 넣되 under[0]가 over[0]보다 크다면 둘의 위치를 바꿔준다.
이를 반복하면 under에는 중간값 아래, over에는 중간값 위만 저장되며 under[0]가 중간값이 된다.
'Week 01 ~ 04 : 알고리즘 문제 풀이' 카테고리의 다른 글
| 파이썬 백준 13334 철로 (0) | 2021.11.16 |
|---|---|
| 파이썬 백준 1715 카드 정렬하기 (0) | 2021.11.15 |
| 파이썬 백준 11279 최대 힙 (0) | 2021.11.15 |
| 파이썬 백준 3190 뱀 (0) | 2021.11.15 |
| 파이썬 백준 11866 요세푸스 문제 0 (0) | 2021.11.15 |