어려움힙

스트림 중앙값

숫자가 하나씩 들어오는 배열 nums가 주어져요. 값이 하나 들어올 때마다 지금까지 들어온 모든 값의 중앙값을 구해서, 그 중앙값들을 순서대로 담은 배열로 반환해요.

중앙값은 값을 정렬했을 때 가운데 값이에요. 개수가 홀수면 가운데 하나, 짝수면 가운데 두 값의 평균이에요.

매번 전체를 정렬하면 느려요. 작은 절반은 최대 힙, 큰 절반은 최소 힙으로 나눠 개수를 비슷하게 유지하면, 두 힙의 꼭대기만 봐서 중앙값을 바로 구할 수 있어요.

JavaScript는 스타터의 MinHeap에 비교자를 뒤집어 최대 힙을 만들어요. 파이썬은 값에 마이너스를 붙여 heapq로 최대 힙을 흉내 내요.

예시

예시 1

입력: nums = [5, 2, 8, 1]
출력: [5, 3.5, 5, 3.5]
설명: [5]→5, [2,5]→(2+5)/2=3.5, [2,5,8]→5, [1,2,5,8]→(2+5)/2=3.5 이에요.

예시 2

입력: nums = [1, 2, 3]
출력: [1, 1.5, 2]

제한 사항

1 ≤ nums.length ≤ 100,000
-100,000 ≤ nums[i] ≤ 100,000

작은 절반을 담는 최대 힙 low, 큰 절반을 담는 최소 힙 high를 둬요. 새 값이 low의 꼭대기보다 작거나 같으면 low에, 아니면 high에 넣고, 두 힙의 크기 차이가 1을 넘지 않게 옮겨 균형을 맞춰요. low가 더 크면 그 꼭대기가 중앙값, 크기가 같으면 두 꼭대기의 평균이 중앙값이에요.

javascript
Copy code
class MinHeap {
  /** @param {(a: any, b: any) => number} [compare] 음수면 a가 먼저 나옵니다. */
  constructor(compare) {
    this.items = [];
    this.compare = compare ?? ((a, b) => (a < b ? -1 : a > b ? 1 : 0));
  }
  get size() {
    return this.items.length;
  }
  peek() {
    return this.items.length > 0 ? this.items[0] : null;
  }
  push(value) {
    const a = this.items;
    a.push(value);
    let i = a.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.compare(a[parent], a[i]) <= 0) break;
      [a[parent], a[i]] = [a[i], a[parent]];
      i = parent;
    }
  }
  pop() {
    const a = this.items;
    if (a.length === 0) return null;
    const top = a[0];
    const last = a.pop();
    if (a.length > 0) {
      a[0] = last;
      let i = 0;
      for (;;) {
        const l = i * 2 + 1;
        const r = l + 1;
        let small = i;
        if (l < a.length && this.compare(a[l], a[small]) < 0) small = l;
        if (r < a.length && this.compare(a[r], a[small]) < 0) small = r;
        if (small === i) break;
        [a[small], a[i]] = [a[i], a[small]];
        i = small;
      }
    }
    return top;
  }
}
function medianStream(nums) {
  const low = new MinHeap((a, b) => b - a);
  const high = new MinHeap((a, b) => a - b);
  const result = [];
  for (const n of nums) {
    if (low.size === 0 || n <= low.peek()) low.push(n);
    else high.push(n);
    if (low.size > high.size + 1) high.push(low.pop());
    else if (high.size > low.size) low.push(high.pop());
    if (low.size > high.size) result.push(low.peek());
    else result.push((low.peek() + high.peek()) / 2);
  }
  return result;
}

이전 문제K개 정렬 리스트 병합

다음 문제계단 오르기

예시 테스트만 실행 (Cmd/Ctrl+Enter)

숨김 테스트까지 채점 (Cmd/Ctrl+Shift+Enter)

에디터를 불러오고 있어요…

코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.