반응형
https://www.acmicpc.net/problem/1655
1655번: 가운데를 말해요
첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1
www.acmicpc.net
import sys
import heapq
N = int(sys.stdin.readline())
nums = [int(sys.stdin.readline()) for _ in range(N)]
max_heap, min_heap = [], []
for n in nums:
if len(min_heap) == len(max_heap):
heapq.heappush(max_heap, (-n, n))
else:
heapq.heappush(min_heap, (n, n))
if min_heap and max_heap[0][1] > min_heap[0][1]:
tmp_max = heapq.heappop(max_heap)[1]
tmp_min = heapq.heappop(min_heap)[1]
heapq.heappush(max_heap, (-tmp_min, tmp_min))
heapq.heappush(min_heap, (tmp_max, tmp_max))
print(max_heap[0][1])
최대힙과 최소힙을 구현하기 위해서,
tuple을 사용한다.
반응형