[1스4코2파] # 240. LeetCode 295. Find Median from Data Stream

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (240차)
[4코1파] 2023.01.13~ (232일차)
[1스4코1파] 2023.04.12~ (143일차)
[1스4코2파] 2023.05.03 ~ (121일차)

Today :

2023.08.31 [240일차]
LeetCode 295. Find Median from Data Stream
https://leetcode.com/problems/find-median-from-data-stream/

295. Find Median from Data Stream

문제 설명

오름차순으로 정렬된 배열에서 중간값(중앙값) median을 return 하는 문제이다. 배열의 길이가 홀수이면 그냥 중앙값을 짝수이면 가운데에 해당하는 배열의 두개의 합의 평균을 리턴함

문제 풀이 방법

리스트를 넣고 sort하고 길이에 따라서 median을 구할 수 있는 방법이 있지만, 비효율적이기 때문에 실시간으로 median을 구하는 방법은 heap을 사용한다.
heap도 minheap, maxheap 둘 다 구현을 해야 하는데,
길이에 따라서 들어오는 실시간 값들을 minheap에 보낼건지 maxheap에 보낼건지 결정한다음 마지막에는 길이에 따라서 minheap의 젤 위에 있는 원소를 return 할 것인지 maxheap에 있는 원소를 return 할 것인지. 짝수개 이면 minheap과 maxheap에 root 원소를 가져와서 평균을 내면 된다 굿

내 코드

 class MedianFinder:

    def __init__(self):
        self.small, self.large = [], []
        
    def addNum(self, num: int) -> None:
        if self.large and num > self.large[0] :
            heapq.heappush(self.large, num)
        else:
            heapq.heappush(self.small, -num)

        if len(self.large) > len(self.small)+1:
            num = heapq.heappop(self.large)
            heapq.heappush(self.small, -num)
        
        if len(self.small) > len(self.large)+1:
            num = -1*heapq.heappop(self.small)
            heapq.heappush(self.large, num)

    def findMedian(self) -> float:
        if len(self.large) > len(self.small):
            return self.large[0]
        elif len(self.small) > len(self.large):
            return -1 * self.small[0]
        else:
            return (-1*self.small[0] + self.large[0] ) / 2

증빙

여담

hard 치고 재밌는 문제이다.
data structure 중에서 가장 힙한 structure는 뭔줄 알아?
바로 heap이야 왜냐? heappop 하니까~ ㅋ