[알고리즘 문제풀이] [파이썬] 백준 #1655 가운데를 말해요

백준 #1655 <가운데를 말해요> 문제 링크 :www.acmicpc.net/problem/1655

문제

예제 입력

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

7
1
5
2
10
-99
7
5

예제 출력

한 줄에 하나씩 N줄에 걸쳐 백준이의 동생이 말해야 하는 수를 순서대로 출력한다.

1
1
2
2
2
2
5

---

백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 따라서 두개의 힙에 숫자를 나눠서 저장하고, 결과적으로 왼쪽 힙의 루트값을 꺼내준다.

코드

# 백준 1655
# 가운데를 말해요
import sys
import heapq
input = sys.stdin.readline

n = int(input().rstrip())

left_heap = [] # 최대 힙
right_heap = [] # 최소 힙
answer = []
for _ in range(n):
    inputNum = int(input().rstrip())

    if len(left_heap) == len(right_heap): # 왼쪽,오른쪽 힙의 길이가 같다면
        heapq.heappush(left_heap, -inputNum) # 왼쪽 힙에 푸쉬해준다
    else:
        heapq.heappush(right_heap, inputNum) # 같지않으면 오른쪽에 푸쉬해준다
    
    if right_heap and -left_heap[0] > right_heap[0]: # 왼쪽힙의 루트가
        mid_r = heapq.heappop(right_heap) # 오른쪽힙의 루트보다 크다면
        mid_l = heapq.heappop(left_heap)  # 왼쪽힙의 루트와 오른쪽 힙의 루트를 바꿔준다
        heapq.heappush(left_heap, -mid_r)
        heapq.heappush(right_heap, -mid_l)
    
    answer.append(left_heap[0])

for nums in answer:
    print(-nums)

알고리즘 문제풀이 모음:

github.com/whwogur/BOJ