💡 첫 풀이

처음에는 규칙성 문제인줄 알고 최대 합을 구현한 뒤 힙의 원소의 개수의 절반만큼 pop을 해서 중간 값을 찾으려고 했다. -> 시간 초과

도저히 모르겠어서 검색해서 방법을 알아냈다. 최대힙과 최소힙을 모두 이용하는 것인데 최대힙 구현할 때 튜플을 썼는데 값을 변경해야 되는 경우가 있어서 에러가 났다. -> 런타임 에러(Type Error)

📝 풀이 방법

첫 풀이 방식으로 시간 초과가 나서 이진 탐색 트리처럼 루트를 중간값으로 하고 왼쪽에 작은 값 오른쪽에 큰 값을 넣으려고 했는데 분류가 우선순위 큐인데 그렇게 하는게 아닌거 같아 검색해봤다.

일단 루트가 중간값이 되어야 하는게 맞다. 그 후에 루트를 기준으로 왼쪽에는 루트보다 작은 값들, 오른쪽에는 루트보다 큰 값들을 배치한다. 이 때, 왼쪽은 최대 힙으로 오른쪽은 최소 힙으로 배치한다.(그래야 중간값이 루트로 나오기 때문)

문제에서
"만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다."
이 구절이 굉장히 중요한데 두 수 중에 작은 수를 말해야 하므로 루트를 왼쪽의 최대힙에 편입시킨다. 즉, 중간값은 왼쪽 최대 힙의 루트가 된다.

주어진 값들을 왼쪽 힙 -> 오른쪽 힙 순서로 차례대로 넣는다. 왼쪽 힙에 먼저 넣는 이유는 왼쪽 힙의 루트가 중간값이 되기 때문이다. 예를 들어 입력이 [5, 4, 3, 2, 1]이 주어졌다면

왼쪽 [5]
오른쪽 [0]

왼쪽 [5]
오른쪽 [4]

왼쪽 [5, 3]
오른쪽 [4]

왼쪽 [5, 3]
오른쪽 [2, 4]

이런 식이다. 단, 오른쪽 힙에 있는 수는 반드시 왼쪽 힙에 있는 수보다 커야 하므로 오른쪽 힙의 루트가 가장 작은값이고 왼쪽 힙의 루트가 가장 큰 값이므로 두 값을 비교해 오른쪽 힙의 루트 값이 왼쪽 힙의 루트 값보다 작다면 두 수를 서로 바꾼 뒤 힙화 한다. 단순 교환만 하면 오답처리된다.

💡 소스코드

import sys, heapq
input = sys.stdin.readline

def insertNum(num):
    temp_right = 0
    temp_left = 0
    if len(left_max_heap)==len(right_min_heap):
        heapq.heappush(left_max_heap, [(-1)*num, num])
    else:
        heapq.heappush(right_min_heap, num)

    if right_min_heap:
        if left_max_heap[0][1] > right_min_heap[0]:
            temp_right = heapq.heappop(right_min_heap)
            temp_left = heapq.heappop(left_max_heap)[1]
            heapq.heappush(right_min_heap, temp_left)
            heapq.heappush(left_max_heap, [(-1)*temp_right, temp_right])

N = int(input())
left_max_heap = []
right_min_heap = []

for i in range(N):
    num = int(input())
    insertNum(num)
    print(left_max_heap[0][1])