[Python]우선순위큐 백준 1655

   문제

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

넣을때마다 정렬해주는 방법과 최대힙과 최소힙을 이용하여 중간값을 찾는 방법이있다.

두 방법다 가능해보이지만  첫번째 방법은 넣을때마다 한칸씩 밀리거나 댕겨야 하는 상황

이 나올수 있기 때문에 그 시간이 오래걸린다.

두번째 방법으로 구현해 보았다.

힙은 heapq모델을 사용하였다. 힙두개를 작성하여 사용하기에는 너무 코드가 길어진다.

import sys
import heapq#heapq는 최소힙만 지원한다 최대힙을 구현하기위해선 -를 곱해서 넣어 주고 꺼낼때 다시 -를 곱해준다
 
 
def middleheap(minheap,maxheap,x):#넣기만함
    if len(maxheap)==len(minheap):#같다면 max힙에 넣어준다
        heapq.heappush(maxheap,-x)
    else:#max힙이 크다면 minheap넣어 균형을 맞춰준다.
        heapq.heappush(minheap,x)
    if minheap and -maxheap[0]>minheap[0]:#minheap이 비어잇지않고 최대 힙의 루트는 항상 최소 힙의 루트보다 작게 유지해준다.
        #최대힙의 루트노드가 더크다면 스왑해주고 다시 힙구조로 만들어주어야한다.
        a=heapq.heappop(minheap)
        b=-heapq.heappop(maxheap)
        heapq.heappush(maxheap,-a)
        heapq.heappush(minheap,b)
 
 
n=int(sys.stdin.readline())
minheap,maxheap=[],[]
while n>0:
    n-=1
    middleheap(minheap,maxheap,int(sys.stdin.readline()))
    print(-maxheap[0])