
이번주 예정된 마지막 알고리즘 문제이다. 백트래킹하다가 자료구조 보니까 살 맛난다..
힙을 두개 사용하는 것이 주요 아이디어이며,
중간값을 뽑아내야하기에 항상 minHeap(최소의 최대)크기가 maxHeap(최대의 최소)크기보다 크거나 같아야 한다.
그래야 -minHeap[0]을 가리킬때 그 위치가 한가운데, 짝수개의 원소라도 작은 수를 가리키게 된다.
import sys,math
input= sys.stdin.readline
import heapq as hq
N=int(input())
minHeap=[]
maxHeap=[]
li=[]
for _ in range(N):
li.append(int(input()))
for i in range(N):
if not minHeap:
hq.heappush(minHeap, -li[i])
else:
# 중간값을 뽑아내야하므로, minHeap의 크기를 maxHeap크기 이상으로 맞춰야 함
if len(minHeap) == len(maxHeap)+1:
if li[i] >= -minHeap[0]:
hq.heappush(maxHeap,li[i])
else:
hq.heappush(maxHeap, - (hq.heappop(minHeap)))
hq.heappush(minHeap,-li[i])
else:
# 이번엔 maxHeap의 최소와 비교
if li[i] > maxHeap[0]:
hq.heappush(minHeap, - (hq.heappop(maxHeap)))
hq.heappush(maxHeap, li[i])
else:
hq.heappush(minHeap, -li[i])
print(-minHeap[0])
'크래프톤정글10기 > 파이썬' 카테고리의 다른 글
| [백준/G4] 탈출 (0) | 2025.09.18 |
|---|---|
| [백준/G4] 빙산 (0) | 2025.09.17 |
| [백준/G4] 스도쿠 (1) | 2025.08.18 |
| [백준/G3]소문난칠공주 (2) | 2025.08.16 |
| DP + 그리디 과제 정리 (4) | 2025.08.06 |