소스코드
import sys
import heapq
input = sys.stdin.readline
N = int(input().strip())
min_heap = []
max_heap = [] # 원소를 추가하는 우선순위가 더 높은 힙(최대힙)
for _ in range(N):
num = int(input().strip())
# 우선적으로 최대힙에 값을 넣음
if (not max_heap) or (num <= -max_heap[0]):
heapq.heappush(max_heap, -num)
else:
heapq.heappush(min_heap, num)
# 균형 맞추기
if len(max_heap) < len(min_heap):
heapq.heappush(max_heap, -heapq.heappop(min_heap))
elif len(max_heap) > len(min_heap) + 1:
heapq.heappush(min_heap, -heapq.heappop(max_heap))
# 결과 출력
print(-max_heap[0])
Python
복사
풀이
•
데이터가 총 10만개입니다. 10만 번째 데이터의 중앙값을 불러야할 때 정렬이 된 상태여야하고 시간 제한은 0.1초로 매우 타이트합니다.
◦
만약 리스트와 기본 정렬 메서드를 사용한다면, 삽입 후 정렬을 해줘야하니 O(NlogN * N)의 시간복잡도를 가지고, 이는 0.1초 시간 제한에서 탈락입니다.
◦
나머지(기본적인 트리, 큐 등…)은 그냥 아닌 것 같다고 생각했습니다.
◦
매 숫자마다 정렬된 상태를 유지하면서 0.1초의 시간복잡도를 만족할만한 자료구조가 힙이라고 생각했습니다.
▪
다만 두 개를 사용해 중앙값을 유지하는 방법(중간값 유지)이 유명하더라구요. 그래서 이를 찾아보고 적용했습니다.
•
개수가 짝수인 경우 중간에 있는 두 수 중 작은 수를 말해야하기 때문에, 최대힙에 우선적으로 원소를 넣어줍니다.
•
또한 두 힙을 이용해 중앙값을 유지하려면, 두 힙의 개수 차이가 1개를 초과하면 안됩니다(즉, 1개 차이까지 허용)
◦
우선적으로 최대힙이 최소힙보다 개수가 적으면 최대힙으로 원소를 옮깁니다.
◦
최대힙이 최소힙보다 개수가 2개 이상 많으면 반대로 최소힙으로 원소를 옮깁니다.