[백준][Python] 1655번 가운데를 말해요

1655번: 가운데를 말해요

 

코드

import heapq
import sys
left = []
right = []
n = int(input())
for _ in range(n):
	num = int(sys.stdin.readline())
	if len(left) == len(right):
		heapq.heappush(left,-num)
	else:
		heapq.heappush(right,num)
	if right and right[0] < -left[0]:
		l = -heapq.heappop(left)
		r = heapq.heappop(right)
		heapq.heappush(left,-r)
		heapq.heappush(right,l)
	print(-left[0])

 

설명

left와 right 2개의 heapq를 이용하였다. left는 숫자에 - 를 붙여 넣어서 최대힙으로, right는 그대로 넣어서 최소힙으로 만들었다.

중간값을 구하는 문제이기 때문에 left부터 숫자를 번갈아가며 넣어주어야 된다. left의 길이가 right와 같으면 left에 숫자를 넣어주고 left가 더 길면 right에 넣어준다.

이때 left에 있는 값보다 right에 있는 값이 더 작은 경우가 발생할 수 있다. 그럴 경우 heappop을 이용해서 각각의 0번 인덱스에 있던 숫자를 빼서 값을 바꿔 넣어준다. ( - 붙여야 됨)

 

left는 최대힙이기 때문에 left[0]의 값이 실제로는 가장 크다. 따라서 -left[0] 값을 출력해주면 된다.