🦖 Programming/Python

[Python] ⭐️백준 알고리즘 1655번 : 가운데를 말해요

박낑깡이 2022. 10. 7. 01:23

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

 

1655번: 가운데를 말해요

첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1

www.acmicpc.net

 

👩‍💻문제 이해

 

 

 

👩‍💻leftheap 과 rightheap의 크기가 같아질 때 중간값 반환 : 성공🌈

import heapq

n = int(input())

leftHeap = []
rightHeap = []
for i in range(n):
    num = int(input())

    if len(leftHeap) == len(rightHeap):
        heapq.heappush(leftHeap, -num)
    else:
        heapq.heappush(rightHeap, num)

    if rightHeap and rightHeap[0] < -leftHeap[0]:
        leftValue = heapq.heappop(leftHeap)
        rightValue = heapq.heappop(rightHeap)

        heapq.heappush(leftHeap, -rightValue)
        heapq.heappush(rightHeap, -leftValue)

    print(-leftHeap[0])