백준.가운데를 말해요.1665.py

https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

1. 두개의 리스트를 이용

2. heappush를 이용해 최소값과 최대값(음수)로 하나의 max_value <-> min_value 중간의 순서를 보장하는 리스트를 만듬

3. 중간값을 참조해서 출력

import heapq
import sys
def solution():
    N = int(sys.stdin.readline().rstrip())

    min_heap = []
    max_heap = []
    result = []
    for _ in range(N):
        num = int(sys.stdin.readline().rstrip())
        
        if len(max_heap) == len(min_heap):
            heapq.heappush(max_heap, (-num, num))
        else:
            heapq.heappush(min_heap, num)

        if min_heap and max_heap[0][1] > min_heap[0]:
            max_value = heapq.heappop(max_heap)[1]
            min_value = heapq.heappop(min_heap)
            heapq.heappush(max_heap, (-min_value, min_value))
            heapq.heappush(min_heap, max_value)

        result.append(str(max_heap[0][1]))
    sys.stdout.write('\n'.join(result))
if __name__ == '__main__':
    solution()