문제

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value and the median is the mean of the two middle values.

For example, for arr = [2,3,4], the median is 3.
For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.
Implement the MedianFinder class:

MedianFinder() initializes the MedianFinder object.
void addNum(int num) adds the integer num from the data stream to the data structure.
double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.

Example 1:

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

Constraints:

$-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.

Follow up:

If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?

Python 풀이

from bisect import insort_left

class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.nums = []

    def addNum(self, num: int) -> None:
        insort_left(self.nums, num)

    def findMedian(self) -> float:
        num_len = len(self.nums)
        return self.nums[num_len//2] if num_len%2==1 else (self.nums[num_len//2-1]+self.nums[num_len//2])/2


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

문제 설명

중앙값 : 크기 순으로 나열된 데이터들 중에서 가운데 위치한 값. 데이터의 개수가 짝수개라면 가운데 두 데이터의 평균값.

정렬된 리스트에서 중앙값을 출력하는 문제이다.
두 함수를 작성해야 하는데, 하나는 빈 리스트를 만들고 거기다 인자로 넘어온 값을 리스트에 추가해야 하는 함수, 두번째는 그 리스트에서 중앙값을 출력하는 함수이다.

코드 설명

C++을 이용했다면 당연히 priority_queue(우선순위 큐)를 이용했겠지만 파이썬에서는 heapq를 이용하면 된다. 그러나 사용법을 잘 몰랐기에 구글링으로 찾아봤는데 bisect라는 모듈을 알게되었다. 이건 쉽게 얘기해서 정렬된 리스트를 유지하면서 값을 추가할 때 유용한 모듈이다. docs.python.org에서 자세한 사용법을 알 수 있다.
bisect.bisect_left(a, x, lo=0, hi=len(a))는 a 라는 리스트에 x라는 값을 추가할 건데(실제로 추가하지는 않음), 정렬된 순서를 유지하면서 추가를 한다면 몇번 인덱스에 추가될 것인지를 리턴한다. 리스트의 범위(시작 인덱스와 끝 인덱스)를 설정할 수 있는데 따로 값을 넣지 않으면 디폴트로 리스트 전체를 비교한다. left가 붙은 이유는 리스트 a에 이미 x가 존재하면 존재하는 값 왼쪽에 추가가 될 것이고 그 인덱스를 리턴한다. 예를 들어서

from bisect import bisect_left, bisect_right
li = [1, 3, 7, 11]
print(bisect_left(li, 5))
print(bisect_right(li, 8))

# 결과
# 1
# 3

print(bisect_left(li, 11))
print(bisect_right(li, 11))
print(li)

# 결과
# 3
# 4
# [1, 3, 7, 11]

리스트에 직접적으로 값이 추가되는 건 아니고 어디 인덱스에 들어가게 되는지 알려준다. 그렇다면 값을 추가하려면 어떻게 해야할까?

bisect.insort_left, bisect.insort_right를 이용하면 된다. bisect.bisect_left, bisect_rihgt는 들어갈 위치를 반환하지만 insort_left, insort_right는 직접 그 자리에 값이 추가가 된다. 이걸 이용해서 이 문제를 풀 수 있다.
참고로 정렬되지 않은 리스트에서 사용하면 원하는 결과가 나오지 않을 수 있다. 이분 탐색을 기준으로 탐색하기 때문에 꼭 정렬된 리스트를 사용하자

중앙값 찾는 것은 어렵지 않으니 패스.