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

 

 

문제 : [백준-1655] 가운데를 말해요 (Python)

출처 :  백준

 

 

---

   사용한 알고리즘  

---

자료 구조 : heapq 를 이용한 탐색

---

---

   Python Code    

import sys
import heapq


sys.stdin = open("input.txt", "r")

N = int(input())

right_heap=[] # 최소 힙
left_heap=[]  # 최대 힙

for _ in range(N):
    temp_input = int(input())

    if len(left_heap)==len(right_heap):
        heapq.heappush(left_heap,(-temp_input,temp_input))
    else :
        heapq.heappush(right_heap, (temp_input, temp_input))

    if right_heap and right_heap[0][1]<left_heap[0][1]:
        left_value = heapq.heappop(left_heap)[1]
        right_value = heapq.heappop(right_heap)[1]
        heapq.heappush(right_heap,(left_value,left_value))
        heapq.heappush(left_heap, (-right_value, right_value))

    print(left_heap[0][1])