(Leetcode) 295 - Find Median from Data Stream
New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time
위 링크에 있는 추천 문제들을 시간이 있을때마다 풀어보려고 한다.
https://leetcode.com/problems/find-median-from-data-stream/description/
hard 문제다.
자바로 풀어봤다.
중간 값 (median)
이 문제는 중간 값을 찾는 문제이다. 중간 값은 말 그대로 중간에 있는 값을 찾는 것이다. 평균과는 다른 개념이다.
아이템의 갯수가 홀수일 경우에는 정렬된 상태에서 가운데 있는 아이템의 값이 중간 값이고. 아이템의 갯수가 짝수일 경우에는 가운데에 있는 두 아이템을 선택하여 평균을 내어 중간 값을 계산한다.
첫 접근
List<Integer> store = new ArrayList<>();
public MedianFinder() {
}
public void addNum(int num) {
store.add(num);
}
public double findMedian() {
Collections.sort(store);
int size = store.size();
if (size % 2 == 0) {
return (double) (store.get(size / 2 - 1) + store.get(size / 2)) / 2;
} else {
return store.get(size / 2);
}
}
이렇게 풀어보면 마지막 테스트 케이스에서 “문제는 해결되었으나, 시간초과” 라는 메시지가 나온다. 따라서 다른 방법을 찾아봐야 했다. 매 번 sort를 해야하는 비용이 있었다.
해결책
PriorityQueue<Integer> maxHeap; // Stores the lower half of the numbers
PriorityQueue<Integer> minHeap; // Stores the upper half of the numbers
public MedianFinder() {
maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
minHeap = new PriorityQueue<>();
}
public void addNum(int num) {
maxHeap.offer(num); // Add to max heap
minHeap.offer(maxHeap.poll()); // Balance the heaps
if (maxHeap.size() < minHeap.size()) {
maxHeap.offer(minHeap.poll());
}
}
public double findMedian() {
if (maxHeap.size() == minHeap.size()) {
return (maxHeap.peek() + minHeap.peek()) / 2.0;
} else {
return maxHeap.peek();
}
}
우선순위 큐(힙) 2개를 사용하여 해결하는 방법이다. 우선순위 큐는 삽입/삭제에 O(logN) 의 시간 복잡도를 가진다. 조회는 루트에 있는 값을 반환하므로 O(1) 이다.