[leetcode][295] Find Median from Data Stream

문제 : https://leetcode.com/problems/find-median-from-data-stream/

---

정렬된 배열의 중앙값을 찾아라. 만약 배열에 짝수개 있다면 중앙값 2개의 평균값을 구해라.

addNum(num) num을 배열에 추가한다.

findMedian() 배열의 중앙값을 구하라.

---

최소힙, 최대힙 으로 푸는 유명한 문제.

왼쪽에는 최대힙, 오른쪽에는 최소힙을 두고 addNum을 할 때 왼쪽 오른쪽 순으로 번갈아가며힙에 수를 넣어준다.

이 때, 왼쪽에 있는 최대힙 원소들은 오른쪽에 있는 최소힙에 있는 원소들보다 모두 작거나 같아야 한다.

따라서 addNum을 할 때 최소힙, 최대힙의 가장 위(앞)에 있는 수를 비교해서 최대힙에 있는 수가 최소힙에 있는 수보다 크다면 두 수를 바꿔서 넣어준다.

ex) 최대 힙(왼) = 2, 1. 최소 힙(오) = 3, 5 가 있는데 4라는 수를 왼쪽 최대 힙에 넣어주면 힙은 다음과 같이 변경된다.

최대 힙(왼) = 4, 2, 1. 최소 힙(오) = 3, 5. 최대 힙에 있는 4가 최소 힙에 있는 3보다 작으므로 두 수를 바꿔준다.

최대 힙(왼) = 3, 2, 1. 최소 힙(오) = 4, 5.

 

findMedian 은 배열에 있는 모든 수의 개수가 홀수인 경우 최대 힙의 가장 위(앞)에 있는 수를 반환한다.

짝수인 경우 최대힙, 최소힙의 가장 위(앞)에 있는 수의 평균을 구해서 반환한다.

 

시간복잡도는 addNum인 경우 O(logN). findMedian은 O(1).

addNum은 좀더 정확히 보면 N을 이때까지 추가한 수의 개수라고 한다면 하나의 힙에는 2/N 개씩 들어가게 되므로 O(log(N/2)).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/295.%20Find%20Median%20from%20Data%20Stream.cpp