[백준][Python] 1655 가운데를 말해요.

계속 쌓이는 값들 중에서 도 뭔가 sort를 계속 해주며 중앙값을 읽어야만 할것같지만 sort를 하다가는 시간초과에 걸릴게 자명.. sort를 하는대신 최대힙과 최소힙 두개를 만들어 읽어야하는값을 그 사이에 계속 컨트롤 해주는 방식으로 힙을 운용한다.

한쪽 힙의 길이가 길어지지 않도록 같은 길이면 왼쪽에 길이가 다르면 오른쪽에 넣어 균형을 맞춰주고

읽어야하는 왼쪽 힙의 value를 기준으로 좌우 크기가 역전되면 팝, 푸시를 통해 정렬된 상태를 유지해준다.

import sys
import heapq


n = int(sys.stdin.readline())
max_h, min_h = [], []
# max_h[0][1]값을 기준으로 큰 값은 min_h, 같거나 작은 값은 max_h에 삽입
for _ in range(n):
    num = int(sys.stdin.readline())
    if len(max_h) == len(min_h):
        heapq.heappush(max_h, (-num, num))
    else:
        heapq.heappush(min_h, (num, num))
    # 왼쪽 힙의 큰값이 오른쪽 힙의 작은 값보다 크면 바꿔줌.
    if len(max_h) >= 1 and len(min_h) >= 1 and max_h[0][1] > min_h[0][1]:
        max_value = heapq.heappop(max_h)[1]
        min_value = heapq.heappop(min_h)[1]
        heapq.heappush(max_h, (-min_value, min_value))
        heapq.heappush(min_h, (max_value, max_value))
        # 왼쪽 힙 첫 값만 읽어줌.
    print(max_h[0][1])