백준: 1655 가운데를 말해요

문제

1655번: 가운데를 말해요

 

문제 풀이

 N개의 수가 차례대로 입력될 때, 중간 값을 출력하여 반환하는 문제이다. 문제를 풀기 위해서는 `heap`을 left, right로 나누고, left의 루트가 중간값이 되도록 로직을 구현하면 쉽게 해결할 수 있다. left는 최대 힙으로 만들고, right는 최소 힙으로 만들면 pop연산을 활용하기 좋다.

 

코드

from sys import stdin
import heapq


if __name__ == '__main__':
    n = int(stdin.readline())
    left, right = [], []

    for _ in range(n):
        num = int(stdin.readline())

        if len(left) == len(right):
            heapq.heappush(left, -num)
        else:
            heapq.heappush(right, num)

        if right and -left[0] > right[0]:
            heapq.heappush(left, -heapq.heappop(right))
            heapq.heappush(right, -heapq.heappop(left))

        print(-left[0])