Find Median from Data Stream

Q: 데이터 스트림에서 중앙값 찾기의 시간 복잡도는 얼마인가요?

두 개의 힙을 사용하면 addNum 은 O(log n) 이며 힙에 최대 세 번 삽입하거나 삭제하고, findMedian 은 두 번 읽으므로 O(1) 입니다. 모든 값이 저장되므로 공간 복잡도는 O(n) 입니다. 대신 매 쿼리마다 정렬하면 findMedian 호출당 O(n log n) 의 비용이 듭니다.

Q: 값을 정렬된 배열에 보관하면 어떨까요?

정렬된 배열은 findMedian 에 O(1) 만에 답하고, 이진 검색은 새 값이 들어갈 위치를 O(log n) 만에 찾습니다. 하지만 값을 삽입하면 그 지점 뒤의 모든 값이 이동하므로, addNum 호출당 O(n) 이 걸립니다.

어려움힙

+10

두 가지 연산을 지원하는 구조를 설계하세요. addNum은 정수를 저장하고, findMedian은 지금까지 저장된 모든 값의 중앙값을 반환합니다. 개수가 홀수이면 중앙값은 가운데 값이고, 짝수이면 가운데 두 값의 평균입니다.

연산 i는 ops[i]이며, values[i]에는 addNum일 때 해당 숫자가, findMedian일 때 0이 들어 있습니다. 빈 구조에서 연산을 순서대로 실행하고, 각 연산마다 문자열 하나를 반환하세요. addNum에는 "null"을, findMedian에는 중앙값을 반환합니다. 중앙값은 "3", "2.5" 또는 "-0.5"처럼 표기하세요. 정수에는 소수점을 붙이지 않고, 0은 "0"으로 표기하며 "-0"은 사용하지 않습니다.

함수

medianStreamOps(ops: string-array, values: integer-array) → string-array

opsstring-array: 실행되는 순서대로 연산
valuesinteger-array: 각 addNum에 대한 숫자, 각 findMedian에 대해 0
반환값string-array: 연산당 답변 하나, 텍스트로

제약 조건

1 ≤ ops.length ≤ 3000
values.length == ops.length
모든 ops[i]는 addNum 또는 findMedian입니다.
-10⁵ ≤ values[i] ≤ 10⁵는 addNum에 해당하고, values[i] == 0은 findMedian에 해당합니다.
findMedian은 최소 하나의 addNum이 호출된 후에만 호출됩니다.

예제

입력: ops = ["addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian"]values = [5, 0, 1, 0, 8, 0, 3, 0]
출력: ["null", "5", "null", "3", "null", "5", "null", "4"]
설명: 1과 5의 중앙값은 (1 + 5) / 2 = 3입니다. 1, 5, 8의 중앙값은 5이고, 1, 3, 5, 8의 중앙값은 (3 + 5) / 2 = 4입니다.

후속 질문

모든 값이 0에서 100 사이에 있다면, 두 연산을 모두 상수 시간에 실행하려면 어떻게 해야 할까요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

중앙값은 데이터의 두 절반 사이에 있으므로 각 절반 내부의 순서는 중요하지 않습니다. 중요한 것은 아래쪽 절반의 최댓값과 위쪽 절반의 최솟값뿐입니다. 두 개의 힙은 바로 이 두 값을 맨 위에 유지합니다. addNum을 수행할 때마다 O(log n)의 비용이 들고, findMedian은 O(1)에 두 힙의 맨 위 값을 읽습니다.

findMedian을 수행할 때마다 정렬

핵심 아이디어

모든 값을 리스트에 저장합니다. findMedian은 리스트를 정렬한 다음 정수 나눗셈으로 인덱스 (total-1)/2와 total/2의 값을 읽습니다. 개수가 홀수이면 같은 인덱스를, 짝수이면 가운데 두 값을 읽습니다. 두 값을 더해 합을 절반으로 나누면 어느 경우든 중앙값을 구할 수 있습니다.

정수로 절반을 계산합니다. 합이 짝수이면 정확히 나누어떨어집니다. 합이 홀수이면 절댓값의 절반 뒤에 .5를 붙이고 합의 부호를 적용하므로, -3은 -1.5가 됩니다.

쿼리마다 다시 정렬합니다. 1,500번 추가하고 매번 쿼리하면 비교 횟수는 약 10^7회입니다. 반면 힙은 수만 번 정도의 연산이면 됩니다.

알고리즘

values 목록을 유지하세요.
addNum x의 경우, x를 추가하고 "null"을 기록하세요.
findMedian의 경우, values를 정렬하고 values[(total-1)/2]와 values[total/2]를 더하세요.
정수로 합계를 텍스트 형태로 절반으로 나누고 기록하세요.

def half_text(total):
    # total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
    if total % 2 == 0:
        return str(total // 2)
    sign = "-" if total < 0 else ""
    return sign + str(abs(total) // 2) + ".5"


class MedianFinder:
    def __init__(self):
        self.values = []

    def addNum(self, x):
        self.values.append(x)

    def findMedian(self):
        self.values.sort()
        total = len(self.values)
        # For an odd count both indexes point at the one middle value.
        return half_text(self.values[(total - 1) // 2] + self.values[total // 2])


def medianStreamOps(ops, values):
    finder = MedianFinder()
    result = []
    for op, x in zip(ops, values):
        if op == "addNum":
            finder.addNum(x)
            result.append("null")
        else:
            result.append(finder.findMedian())
    return result

두 힙으로 중앙값에서 나누기

핵심 아이디어

값을 아래쪽 절반인 low와 위쪽 절반인 high로 나누세요. low의 모든 값은 high의 모든 값보다 작거나 같아야 하고, low의 크기는 high와 같거나 하나 더 커야 합니다. 중앙값은 low의 최댓값이며, 값의 개수가 짝수이면 low의 최댓값과 high의 최솟값의 평균입니다. low에는 최대 힙을, high에는 최소 힙을 사용하면 해당 값들이 맨 위에 오도록 유지할 수 있습니다.

새 값이 low의 맨 위 값보다 작거나 같으면 low에 넣고, 그렇지 않으면 high에 넣습니다. 크기가 서로 달라지면 맨 위 값을 옮기세요. 이 값은 다른 절반에 가장 가까운 값이므로 순서가 유지됩니다. 추가 작업은 몇 번의 힙 연산으로 이루어지며, 시간 복잡도는 O(log n)입니다. 힙이 변경될 때마다 복사하는 R에서는 O(n)입니다.

첫 번째 예시에서 네 번 추가한 후 low에는 3과 1이, high에는 5와 8이 들어 있습니다.

알고리즘

아래쪽 절반을 위한 최대 힙 low와 위쪽 절반을 위한 최소 힙 high를 유지합니다.
addNum x: low가 비어 있거나 x가 최상위 값보다 작거나 같으면 x를 low에 넣고, 그렇지 않으면 high에 넣습니다.
low에 high보다 값이 두 개 더 많으면 low의 최상위 값을 high로 옮깁니다. high에 low보다 값이 더 많으면 high의 최상위 값을 low로 옮깁니다.
findMedian: low가 더 크면 최상위 값을 기록합니다. 그렇지 않으면 두 최상위 값을 더한 다음 정수 나눗셈으로 합을 절반으로 나눕니다.

import heapq


def half_text(total):
    # total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
    if total % 2 == 0:
        return str(total // 2)
    sign = "-" if total < 0 else ""
    return sign + str(abs(total) // 2) + ".5"


class MedianFinder:
    def __init__(self):
        self.low = []   # the smaller half; heapq is a min-heap, so it stores -x to keep the largest on top
        self.high = []  # the larger half, smallest on top

    def addNum(self, x):
        if not self.low or x <= -self.low[0]:
            heapq.heappush(self.low, -x)
        else:
            heapq.heappush(self.high, x)
        # Rebalance: low holds as many values as high, or one more.
        if len(self.low) > len(self.high) + 1:
            heapq.heappush(self.high, -heapq.heappop(self.low))
        elif len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))

    def findMedian(self):
        if len(self.low) > len(self.high):
            return str(-self.low[0])
        return half_text(-self.low[0] + self.high[0])


def medianStreamOps(ops, values):
    finder = MedianFinder()
    result = []
    for op, x in zip(ops, values):
        if op == "addNum":
            finder.addNum(x)
            result.append("null")
        else:
            result.append(finder.findMedian())
    return result

함정과 경계 사례

값이 아니라 크기를 기준으로 힙을 선택하는 것. 비교하지 않고 더 작은 힙에 값을 넣으면 두 부분의 순서가 깨지고, 각 힙의 맨 위 값이 더 이상 중앙값이 아니게 됩니다.
일반 정수 나눗셈으로 절반을 구하는 것. C와 Java에서는 -1 / 2가 0이므로, .5를 덧붙이면 -0.5가 0.5로 출력됩니다. Python에서는 -3 // 2가 -2이므로 -1.5가 -2.5로 출력됩니다. 일부 언어에서는 부동 소수점 값이 3.0 또는 2.500000으로 출력됩니다.
최소 힙에서 low를 음수로 저장하고, 맨 위 값을 읽거나 값을 high로 옮길 때 다시 음수 부호를 붙이는 것을 잊는 것.
-0을 쓰는 것. 중앙값 -1과 1의 합은 0이며, 답은 "0"입니다.

자주 묻는 질문3

데이터 스트림에서 중앙값 찾기의 시간 복잡도는 얼마인가요?

두 개의 힙을 사용하면 addNum은 O(log n)이며 힙에 최대 세 번 삽입하거나 삭제하고, findMedian은 두 번 읽으므로 O(1)입니다. 모든 값이 저장되므로 공간 복잡도는 O(n)입니다. 대신 매 쿼리마다 정렬하면 findMedian 호출당 O(n log n)의 비용이 듭니다.

값을 정렬된 배열에 보관하면 어떨까요?

정렬된 배열은 findMedian에 O(1) 만에 답하고, 이진 검색은 새 값이 들어갈 위치를 O(log n) 만에 찾습니다. 하지만 값을 삽입하면 그 지점 뒤의 모든 값이 이동하므로, addNum 호출당 O(n)이 걸립니다.

모든 값을 저장하지 않고도 데이터 스트림의 정확한 중앙값을 찾을 수 있나요?

일반적으로는 그렇지 않습니다. 지금까지 본 어떤 값이든 다음에 무엇이 들어오느냐에 따라 나중에 중앙값이 될 수 있으므로, 정확한 답을 구하려면 모든 값이 필요합니다.

def medianStreamOps(ops, values):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

인자들

ops = ["addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian"]
values = [5, 0, 1, 0, 8, 0, 3, 0]

예상 출력

["null", "5", "null", "3", "null", "5", "null", "4"]