← 전체 회차
a-070-find-median-from-data-stream2026-07-26hardleetcode #295neetcode150

데이터 스트림에서 중앙값 구하기

#two-pointers#design#sorting#heap-priority-queue#data-stream
↗ leetcode #295 · a-070-find-median-from-data-stream
01

문제

· problem
P.a-070-find-median-from-data-stream

데이터 스트림에서 중앙값 구하기

↗ leetcode #295

중앙값(median)은 정렬된 정수 리스트의 중간 값입니다. 리스트의 크기가 짝수인 경우 중간 값이 없으므로, 중앙값은 두 중간 값의 평균입니다. MedianFinder 클래스를 구현하세요: - MedianFinder()는 MedianFinder 객체를 초기화합니다. - void addNum(int num)은 데이터 스트림에서 정수 num을 데이터 구조에 추가합니다. - double findMedian()은 지금까지의 모든 원소의 중앙값을 반환합니다. 실제 답의 10^-5 이내의 오차가 허용됩니다.

제약
  • · -10^5 ≤ num ≤ 10^5
  • · There will be at least one element in the data structure before calling findMedian
  • · At most 5 × 10^4 calls will be made to addNum and findMedian
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
[null, null, null, 1.5, null, 2.0]
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    두 힙을 '균형 잡혀있다'는 것은 정확히 무엇을 의미하나요?
  • ☐
    왜 작은 수들을 담는 힙에 음수를 저장하나요?
  • ☐
    총 원소 개수가 홀수일 때와 짝수일 때 중앙값을 어떻게 다르게 반환하나요?
  • ☐
    새로운 수를 어느 힙에 먼저 추가할지 어떻게 결정하나요?
  • ☐
    정렬된 배열 대신 두 힙을 사용하는 이유는 무엇인가요?
  • ☐
    모든 작은 수를 최소 힙에, 큰 수를 최대 힙에 저장해야 하나요?
  • ☐
    findMedian()의 시간 복잡도가 O(1)인 이유는 무엇인가요?
  • ☐
    힙 재조정 후 total count가 변하나요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 두 힙 초기화
○
self.small, self.large = [], []  # maxHeap, minHeap (python default)
○
self.small, self.large = set(), set()
○
self.heap = []
step 2· 수를 적절한 힙에 추가│ 중첩
○
if self.large and num > self.large[0]:
○
heapq.heappush(self.small, num); heapq.heappush(self.large, num)
○
if num > 0: heapq.heappush(self.large, num) else: heapq.heappush(self.small, num)
step 3· 작은 힙 크기 초과 시 재조정│ 중첩
○
if len(self.small) > len(self.large) + 1:
○
if len(self.small) > len(self.large): val = -1 * heapq.heappop(self.small); heapq.heappush(self.large, val)
○
if len(self.small) > len(self.large): val = heapq.heappop(self.small); heapq.heappush(self.large, -1 * val)
step 4· 큰 힙 크기 초과 시 재조정│ 중첩
○
if len(self.large) > len(self.small) + 1:
○
if len(self.large) > len(self.small) + 1: val = heapq.heappop(self.large); heapq.heappush(self.small, val)
○
if len(self.large) >= len(self.small): val = heapq.heappop(self.large); heapq.heappush(self.small, -1 * val)
step 5· 작은 힙이 크면 그 최댓값 반환│ 중첩
○
if len(self.small) > len(self.large):
○
if len(self.small) > len(self.large): return self.small[0]
○
if len(self.small) >= len(self.large): return -1 * self.small[0]
step 6· 큰 힙이 크면 그 최솟값 반환│ 중첩
○
elif len(self.large) > len(self.small):
○
elif len(self.large) > len(self.small): return -1 * self.large[0]
○
elif len(self.large) >= len(self.small): return self.large[-1]
step 7· 크기가 같으면 두 최상단의 평균 반환│ 중첩
○
return (-1 * self.small[0] + self.large[0]) / 2.0
○
return (self.small[0] + self.large[0]) / 2.0
○
return (-1 * self.small[0] + self.large[0]) / 2
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class MedianFinder:
2
    def __init__(self):
3
        """
4
        initialize your data structure here.
5
        """
6
        # two heaps, large, small, minheap, maxheap
7
        # heaps should be equal size
8
        self.small, self.large = [], []  # maxHeap, minHeap (python default)
9
10
    def addNum(self, num: int) -> None:
11
        if self.large and num > self.large[0]:
12
            heapq.heappush(self.large, num)
13
        else:
14
            heapq.heappush(self.small, -1 * num)
15
16
        if len(self.small) > len(self.large) + 1:
17
            val = -1 * heapq.heappop(self.small)
18
            heapq.heappush(self.large, val)
19
        if len(self.large) > len(self.small) + 1:
20
            val = heapq.heappop(self.large)
21
            heapq.heappush(self.small, -1 * val)
22
23
    def findMedian(self) -> float:
24
        if len(self.small) > len(self.large):
25
            return -1 * self.small[0]
26
        elif len(self.large) > len(self.small):
27
            return self.large[0]
28
        return (-1 * self.small[0] + self.large[0]) / 2.0
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
→
[null, null, null, 1.5, null, 2.0]
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.