파이썬 백준 1655 가운데를 말해요

정글러 2021. 11. 15. 23:50

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]가 중간값이 된다.