https://www.acmicpc.net/problem/1655
1655번: 가운데를 말해요첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1www.acmicpc.net
heap을 두개쓴다
[최대힙] (중간값) [최소힙]
중간값도 결국엔 힙에들어가야 하므로
최대힙의 루트를 중간값으로 정한다.
ex 1,2,3,
[2,1],[3]
왼쪽은 l , 오른쪽을 r 이라 하겠다.
새로운 수가 들어오면,
l이 r 보다 원소가 많으면 r에, 아니면 기준인 l 에 heappush 시킨다.
이때, r의 루트가 (r에서 가장 작은 수가) l의루트(l에서 가장 큰 수) 보다 작다면
서로의 루트를 바꿔준다. (l의 루트가 다시 중간값이 된다)
어렵다
import sysimport heapqinput=sys.stdin.readline
left,right=[],[] #최대힙, 최소힙 중간값을 left의 root로 할거임n=int(input().rstrip())
for _ in range(n): num=int(input().rstrip()) if len(left)==len(right):
heapq.heappush(left,-num) else: heapq.heappush(right,num)
if right and -left[0] > right[0]: #만일 left의 루트, 즉 중간값이 right의 루트, right의 최솟값보다 크다면
lr=-heapq.heappop(left) rr=-heapq.heappop(right)
##각각의 루트를 바꿔준다. (중간값을 바꾸기 위해서) heapq.heappush(right,lr)
heapq.heappush(left,rr) print(-left[0])