가운데를 말해요는 특정 방법이 생각나지 않으면 정말 풀기 어려운 문제인것 같다.
파이썬으로 중앙값 실시간으로 구하기 (두 개의 힙 활용)
많은 숫자들을 입력받으면서 실시간으로 중앙값을 구해야해서 단순 배열로하기에는 시간 초과가 날 수 있다.
매번 수를 입력받을 때마다 지금까지 입력된 수들 중에서 중앙값을 즉시 출력.
아이디어: 두 개의 힙 사용
maxHeap: 현재까지 입력된 수 중 작은 절반을 저장 (최댓값이 루트, -maxHeap[0])
minHeap: 큰 절반을 저장 (최솟값이 루트)
중앙값은 항상 maxHeap의 루트에 위치하게 한다.
import heapq
import sys
n = int(sys.stdin.readline()) # 전체 숫자의 개수 입력
maxHeap = []
minHeap = []
for i in range(n):
num = int(sys.stdin.readline())
if len(maxHeap) == len(minHeap):
heapq.heappush(maxHeap, -num)
else:
heapq.heappush(minHeap, num)
if minHeap and minHeap[0] < -maxHeap[0]:
minValue = heapq.heappop(maxHeap)
maxValue = heapq.heappop(minHeap)
heapq.heappush(maxHeap, -maxValue)
heapq.heappush(minHeap, -minValue)
print(-maxHeap[0])동작 원리 요약
1. maxHeap은 항상 중앙값 이하의 숫자를 저장
2. minHeap은 중앙값 초과의 숫자를 저장
3. 입력받은 숫자를 두 힙에 균형 있게 배치
4. 두 힙의 루트값을 비교해 중앙값 조건을 깨면 교환
5. 중앙값은 항상 maxHeap 루트값
| 입력값 | maxHeap (음수로 저장) | minHeap | 출력 (중앙값) |
|---|---|---|---|
| 1 | [-1] | [] | 1 |
| 5 | [-1] | [5] | 1 |
| 2 | [-2, -1] | [5] | 2 |
| 10 | [-2, -1] | [5, 10] | 2 |
| -99 | [-2, -1, 99] | [5, 10] | 2 |
| 7 | [-2, -1, 99] | [5, 10, 7] | 2 |
| 5 | [-5, -2, 99, -1] | [5, 10, 7] | 5 |
