문제

• Median을 찾는 class를 만들어라
• 생성자에서 초기화 하고
• addNum에서 자료구조에 자료 추가
• findMedian 하면 중앙값 리턴

풀이

• hard 문제인데 그닥 hard하지 않을 것 같은데....?
• 일단 median 라이브러리로 풀어보고, 성능 안나오면 heap 사용해야겠다

statistics.median

from statistics import median

class MedianFinder:

    def __init__(self):
        self.numbers = []
        
    def addNum(self, num: int) -> None:
        self.numbers.append(num)

    def findMedian(self) -> float:
        return median(self.numbers)


# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()

시간초과.......

sort

class MedianFinder:
    def __init__(self):
        self.numbers = []
        self.length = 0

    def addNum(self, num: int) -> None:
        self.numbers.append(num)
        self.length += 1

    def findMedian(self) -> float:
        self.numbers.sort()
        if self.length % 2 == 0:
            # even
            return sum(self.numbers[self.length // 2 - 1:self.length // 2 + 1]) / 2
        else:
            return self.numbers[self.length // 2]

heapq

from heapq import heappush, heappop

class MedianFinder:
    def __init__(self):
        self.numbers = []
        self.length = 0

    def addNum(self, num: int) -> None:
        heappush(self.numbers, num)
        self.length += 1

    def findMedian(self) -> float:
        if self.length % 2 == 0:
            # even
            count = self.length//2-1
            copied = self.numbers.copy()
            for _ in range(count):
                heappop(copied)
            return (heappop(copied)+heappop(copied)) / 2
        else:
            count = self.length//2
            copied = self.numbers.copy()
            for _ in range(count):
                heappop(copied)
            return heappop(copied)

뿌엥 이것도 시간초과,,,,,,,,,,,,

Discussion보고 공부해야될것같은데 배고프니까 오늘은 여기까지