이번 문제는 두개의 힙을 사용하여 해결하였다. 처음에는 입력을 받을 때에 이분 탐색을 통해 입력값이 들어갈 자리를 찾아 들어가도록 하고, 가운데 값을 인덱스로 접근하여 매 입력마다 출력되도록 하였다. 그러나 시간초과가 발생하였고, 다른 방법이 생각나지 않아 고민하던 중 다른 사람의 코드를 보고 힌트를 얻을 수 있었다.

바로 힙을 2개 사용하는 것이다. 파이썬에서의 heapq는 최소힙을 지원한다. heapq에 들어가는 수에 -를 붙이면 최대힙으로도 사용이 가능하다. 이렇게 최대힙과 최소힙을 사용하여 이 문제를 해결할 수 있다.

최대힙을 max_hp, 최소힙을 min_hp으로 선언하고, 두 힙에 중간 값을 기준으로 나눠들어가게 한다.

입력 예시로 주어진 1, 5, 2, 10, -99, 7 ,5가 입력값으로 들어오는 경우,

• num=1 -> max_hp=[-1], min_hp=[]
  -> 1 출력
• num=5 -> max_hp=[-1], min_hp=[5]
  -> 1 출력
• num=2 -> max_hp=[-2, -1], min_hp=[5]
  -> 2 출력
• num=10 -> max_hp=[-2, -1], min_hp=[5, 10]
  -> 2 출력
• num=-99 -> max_hp=[-2, -1, 99], min_hp=[5, 10]
  -> 2 출력
• num=7 -> max_hp=[-2, -1, 99], min_hp=[5, 7, 10]
  -> 2 출력
• num=5 -> max_hp=[-5, -2, -1, 99], min_hp=[5, 7, 10]
  -> 5 출력

여기서 중요한 점은 최대힙의 가장 앞의 수*(-1)의 값은 최소힙의 가장 앞의 수보다 작거나 같아야 한다. 그래야만 중간값을 기준으로 반으로 나눈 형태가 유지된다. 그리고 위와 같은 순서로 양쪽 힙에 수가 입력되게 되면 어떤 상황에서든 max_hp의 가장 앞의 수*(-1)을 출력하게 된다. 이 수가 가운데 값이 되기 때문이다.

• n을 입력받는다.
• max_hp, min_hp을 선언한다.
• n번 반복하는 for문을 돌린다.
  -> num을 입력받는다.
  -> 만약 max_hp의 길이와 min_hp의 길이가 같을 경우,
  --> max_hp에 -num을 넣는다.
  -> 그 외의 경우,
  --> min_hp에 num을 넣는다.
  -> max_hp과 min_hp이 비어있지 않고, max_hp[0]*-1이 min_hp[0]보다 클 경우,
  --> 임시 변수 mx에 max_hp.popleft()*-1을 저장한다.
  --> 임시 변수 mn에 min_hp.popleft()*-1을 저장한다.
  --> max_hp에 mn을 넣는다.
  --> min_hp에 mx를 넣는다.
  -> max_hp[0]*-1을 출력한다.

Code

import sys
import heapq
input=sys.stdin.readline
n=int(input())
max_hp, min_hp=[], []
for _ in range(n):
    num=int(input())
    if len(max_hp)==len(min_hp):
        heapq.heappush(max_hp, -num)
    else:
        heapq.heappush(min_hp, num)
    if max_hp and min_hp and max_hp[0]*-1>min_hp[0]:
        mx=heapq.heappop(max_hp)*-1
        mn=heapq.heappop(min_hp)*-1
        heapq.heappush(max_hp, mn)
        heapq.heappush(min_hp, mx)
    print(max_hp[0]*-1)