가운데를 말해요

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

"""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()