problem-1655

과정
1. q1, q2 두 개의 리스트를 생성 -> q1과 q2는 오름차순으로 정렬되어있고, max(q1)<=min(q2)
2. heapq를 이용하여 q1의 최댓값과 q2의 최솟값을 알아냄
3. q1의 마지막 원소를 중앙값으로 둠 -> len(q1)>=len(q2), len(q1)-len(q2)<2
4. 만약 현재 len(q1)이 len(q2)보다 이미 하나가 많다면 무조건 q2가 하나 늘어나야함

4-1. q2가 비어있을경우와 있을 경우를 나누어서 생각
4-2. q2가 있을 경우, q2의 최솟값과 num을 비교 -> num이 더 클 경우 q2에 추가 || 작을 경우 q1의 최댓값과 비교하여 max(q1)<=num이면 q2로 추가하고, max(q1)>=num이면 q1에 추가하고 max(q1)을 q2에 추가함

5. len(q1)과 len(q2)가 같다면, q1에 무조건 추가해야함.

   5-1. num이 q2의 최솟값보다 클 경우, q2의 최솟값을 q1에 넣고 num을 q2에 넣음
   5-2. num이 q2의 최솟값보다 작을 경우, 그대로 q1에 넣음
   단, 이 넣고 빼는 과정은 heapq 모듈을 사용하기 때문에 q1에서의 최댓값을 뽑기 위해서는 각 원소에 -1을 곱해서 넣어줘야함.

import sys
import heapq
input = sys.stdin.readline
n = int(input())
q1, q2 = [], []
result = []
for _ in range(n):
    num = int(input())
    if not q1:
        heapq.heappush(q1, -1*num)
        result.append(num)
        continue

    temp = -1*heapq.heappop(q1)  # 하나를 뺌
    if len(q1) == len(q2):  # q2에 넣어야함
        if not q2:  # q2가 없을때 q1에서 하나 뺀거랑 인풋이랑 비교해서 넣음
            heapq.heappush(q2, max(temp, num))
            heapq.heappush(q1, -1*min(temp, num))
        else:  # q2가 있을때 q2의 최솟값 temp2를 뽑아서 num이랑 비교
            temp2 = heapq.heappop(q2)
            if num >= temp2:  # num이 temp2보다 크면 무조건 q2로 바로들어감
                heapq.heappush(q2, temp2)
                heapq.heappush(q2, num)
                heapq.heappush(q1, -1*temp)
            else:  # num이 temp2보다 작으면 temp와 비교해서
                if temp <= num:  # temp보다 크거나 같으면 바로 q2로 집어넣음
                    heapq.heappush(q2, num)
                    heapq.heappush(q2, temp2)
                    heapq.heappush(q1, -1*temp)
                else:  # temp보다 작으면 num이 q1으로 들어가고 temp가 q2로 들어감
                    heapq.heappush(q1, -1*num)
                    heapq.heappush(q2, temp)
                    heapq.heappush(q2, temp2)
    else:  # q1에 넣어야함 ->적어도 q2에 하나는 있음
        temp2 = heapq.heappop(q2)
        if num > temp2:  # num이 q2의 최솟값보다 크면 q2의 최솟값을 q1에다 넣고 num을 q2에 넣음
            heapq.heappush(q2, num)
            heapq.heappush(q1, -1*temp2)
            heapq.heappush(q1, -1*temp)
        else:  # num이 q2의 최솟값보다 작으면 바로 q1에 집어넣음
            heapq.heappush(q2, temp2)
            heapq.heappush(q1, -1*num)
            heapq.heappush(q1, -1*temp)

    ans = heapq.heappop(q1)*-1
    heapq.heappush(q1, ans*-1)
    result.append(ans)

for r in result:
    print(r)

time: 120분
ps. 구현에 시간이 오래걸렸다.