====== 가운데를 말해요 ======

===== 풀이 =====
  * 데이터가 계속 추가될때마다 median을 갱신하는 문제이다. 
  * 이 문제는 [[ps:우선순위큐#Running Median]] 이라고도 불리는데, max힙과 min힙, 두개의 힙을 사용해서 구현 가능하다. 
  * 이렇게 구현할 경우, 일반 max힙이나 min힙이 하는 것처럼, O(1)에 peek, O(logn)에 push와 pop이 가능하다. 자세한 것은 링크 참조.
  * 이 문제에서는 n번의 push와 n번의 peek가 필요하므로 총 시간복잡도는 O(nlogn).
  * [[ps:Order Statistic Tree]]를 사용하는 것도 생각해볼 수는 있다. 일반적으론는 heap으로 처리 가능한 것을 Order Statistic Tree로 처리하려 하면 훨씬 느려지기는 하지만, 이 문제의 경우 SegmentTree로 구현한 Order Statistic Tree를 쓰면 O(nlogn)이 아닌 O(nlogk)가 되고, k<=20000 으로 n<=100000보다 작으니까 고려해 볼수도 있긴 하다. 그러나 그렇게 하면 TLE가 난다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 1655. 가운데를 말해요".

- Problem link: https://www.acmicpc.net/problem/1655
- Solution link: http://www.teferi.net/ps/problems/boj/1655
"""

import heapq
import sys

INF = float('inf')


def main():
    N = int(sys.stdin.readline())
    max_heap = []
    min_heap = []
    median = INF
    for _ in range(N):
        num = int(sys.stdin.readline())
        if num < median:
            heapq.heappush(max_heap, -num)
            if len(max_heap) > len(min_heap) + 1:
                heapq.heappush(min_heap, -heapq.heappop(max_heap))
        else:
            heapq.heappush(min_heap, num)
            if len(max_heap) < len(min_heap):
                heapq.heappush(max_heap, -heapq.heappop(min_heap))
        median = -max_heap[0]
        print(median)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_2}}