[백준] - 1655 파이썬 python

풀이

입력 차례가 홀수면 왼쪽 리스트에 추가하고, 짝수면 오른쪽 리스트에 추가를 합니다.

(각 리스트의 0번째는 가운데거나 가장 가까운 수로 왼 리스트를 역순으로(maxheap)으로 정렬,

오른쪽 리스트는 minheap으로 정렬)  

왼쪽 첫번째가 오른쪽 첫번째보다 항상 작도록 하여 입력의 개수가 짝수일 경우 왼쪽 첫번째가 가운데 작은 숫자가 되도록 합니다.

import sys
import heapq
input = sys.stdin.readline


def sol1655():

    left = []
    right = []

    n = int(input())

    for i in range(1, n+1):
        num = int(input())
        if len(left) == len(right):
            heapq.heappush(left,(-num,num))
        else:
            heapq.heappush(right,(num,num))

        if right and left[0][1] > right[0][1]:
            left_value = heapq.heappop(left)[1]
            right_value = heapq.heappop(right)[1]
            heapq.heappush(right, (left_value, left_value))
            heapq.heappush(left, (-right_value, right_value))
        print(left[0][1])


if __name__ == '__main__':
    sol1655()