공부한 것
- LeetCode #295. Find Median from Data StreamFind Median from Data Stream - LeetCodeCan you solve this real interview question? Find Median from Data Stream - 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: * -105 <= num <= 105 * There will be at least one element in the data structure before calling findMedian. * At most 5 * 104 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?
https://leetcode.com/problems/find-median-from-data-stream/
- 방법 1: 이진 트리로 스트림 데이터(숫자들)를 넣은 후 중위 순회를 반 진행하여 중위값을 반환하기 ⇒ 시간 초과로 해답이 통과하지 못함.
- 방법 2: 최대 힙에 더 작은 수를, 최소 힙에 더 큰 수들을 나누어 담은 후 각 힙에서 O(1) 시간으로 얻을 수 있는 최대값과 최소값으로 중위값을 구하기 ⇒ 통과함
방법 2 풀이 코드:
최대 힙과 최소 힙을 따로 구현하였다. leetcode에서 직접 풀 때는 디폴트로 제공되는 priority queue나 queue를 사용할 수도 있다(참고: “언어별 환경(사용 가능한 라이브러리 구성)에 대하여”)
최소 힙 코드:
class MinHeap { private heap: number[]; constructor() { this.heap = []; } //^ 삽입한 요소를 힙 구조에 맞게 위치 조정(heapify) - Bubble up // Time complexity: O(log N) // Space complexity: O(1) private bubbleUp() { // 마지막 요소에서 시작. 부모와 교체할 때마다 그 위치로 index 값이 조정됨. 그렇게 업데이트되는 바뀌는 위치가 root 노드에 도달하기까지 아래 루프를 반복한다. let index = this.heap.length - 1; while (index > 0) { // 해당 요소의 부모 노드 위치를 계산해서 그 값을 parent로 지정한다. heap은 왼쪽부터 꽉꽉 채워서 차례로 들어가는 반 완전 이진 트리(?)로 본다. const element = this.heap[index]; const parentIndex = Math.floor((index - 1) / 2); const parent = this.heap[parentIndex]; // 새로 삽입한 요소와 부모 노드를 비교하여 위치를 조정: // 만약 지금 요소가 부모보다 크거나 같으면 전체 루프를 멈춘다. if (element >= parent) break; // 만약 부모보다 값이 작으면 자리를 바꾼다. this.heap[index] = parent; this.heap[parentIndex] = element; // (부모와 바꿔서) 새롭게 위치한 자리를 새로운 index로 삼는다. index = parentIndex; // 자신보다 작은 부모를 만나거나 루트에 도달하기까지 과정을 반복한다. } } //^ 추출한 요소를 힙 구조에 맞게 위치 조정(heapify) - Bubble Down // Time complexity: O(log N) // Space complexity: O(1) private bubbleDown() { // 앞의 요소부터 시작한다. let index = 0; const element = this.heap[index]; // 무한 루프를 돌면서 while (true) { // 현재 요소의 두 자식 위치를 구한다. const leftChildIndex = index * 2 + 1; const rightChildIndex = index * 2 + 2; let leftChild, rightChild; let swapTarget = null; // 각 자식마다, 자식의 위치가 실제 존재하는 노드라면(=heap의 길이 내라면) 그 값을 leftChild, rightChild에 저장한다. 또 각 자식이 현재 요소보다 작으면 자리를 바꿔야 하므로, 바꿀 타겟이 되는 위치 변수 swapTarget에 자식의 위치를 따로 저장한다. if (leftChildIndex < this.heap.length) { leftChild = this.heap[leftChildIndex]; if (leftChild < element) { swapTarget = leftChildIndex; } } // 그래서 만약 "왼 자식은 그대로 두고 오른 자식만 바꿔야 하든지", "왼 자식도 바꿔야 하는데 오른 자식이 왼보다 더 작다면(더 작은 쪽을 위로 올려야 하므로)" 오른 자식을 바꿀 대상 swapTarget으로 삼는다. if (rightChildIndex < this.heap.length) { rightChild = this.heap[rightChildIndex]; if ((!swapTarget && rightChild < element) || (swapTarget && rightChild < leftChild)) { swapTarget = rightChildIndex; } } // 교체할 대상이 없다면 현재 루프를 break한다. 루프 전체에서 break하는 부분이 여기뿐으로, 두 자식 중 더이상 바꿀 대상이 없는 경우에만 무한 루프를 멈추게 된다. if (!swapTarget) break; // 교체할 대상이 있다면 현재 노드와 교체한다. this.heap[index] = this.heap[swapTarget]; this.heap[swapTarget] = element; // 다시 '현재 요소'의 위치를 바꾼 타겟 위치로 지정하고 루프를 계속한다. index = swapTarget; } } //^ 요소를 삽입 // Time & Space complexity: bubbleUp()과 동일 insert(value: number) { // heap배열의 마지막에 요소를 삽입하고, 알맞은 위치로 찾아가도록 this.bubbleUp() 활용 this.heap.push(value); this.bubbleUp(); } //^ 최소 요소 추출 // Time & Space complexity: bubbleDown()과 동일 popMin() { // 제일 앞의 요소가 반환 대상이다.(아직 안뽑음) const min = this.heap[0]; // 제일 뒤의 요소를 뽑고서(?) 만약 heap이 비게 됐다면 이게 곧 반환할 최소값이라는 소리이므로 그대로 반환한다. const end = this.heap.pop(); // 만약 heap 길이가 아직 0이 아니면 뽑은 수를 제일 앞 자리로 덮어씌워준다. 그리고 거기서부터 bubbleDown해서 제자리를 찾도록 한다. if (this.heap.length > 0) { this.heap[0] = end; this.bubbleDown(); } return min; } //^ 힙의 길이를 반환 getLength() { return this.heap.length; } //^ 최소값을 반환(추출 없이) getMin() { return this.heap[0]; } }
최대 힙 코드:
// MinHeap과 거의 비슷하므로 주석은 생략한다. class MaxHeap { private heap: number[] constructor() { this.heap = []; } //^ heap의 맨 끝 요소를 제자리로 끌어올리기 private bubbleUp() { // 부모와 비교하여 더 클 때만 자리를 교체한다. let index = this.heap.length - 1; while (index > 0) { let element = this.heap[index]; let parentIndex = Math.floor((index - 1) / 2); let parent = this.heap[parentIndex]; if (element <= parent) break; this.heap[parentIndex] = element; this.heap[index] = parent; index = parentIndex; } } //^ heap의 맨 앞 요소를 제자리로 끌어내리기 private bubbleDown() { // 존재하는 자식 중 나보다 더 큰 최대 자식과 자리를 교체한다. let index = 0; const element = this.heap[index]; while (true) { let leftChildIndex = index * 2 + 1; let rightChildIndex = index * 2 + 2; let leftChild, rightChild; let swapTarget = null; if (leftChildIndex < this.heap.length) { leftChild = this.heap[leftChildIndex]; if (element < leftChild) { swapTarget = leftChildIndex; } } if (rightChildIndex < this.heap.length) { rightChild = this.heap[rightChildIndex]; if ((swapTarget === null && element < rightChild) || (swapTarget !== null && leftChild < rightChild)) { swapTarget = rightChildIndex; } } if (swapTarget === null) break; this.heap[index] = this.heap[swapTarget]; this.heap[swapTarget] = element; index = swapTarget; } } //^ 요소를 삽입 insert(num: number) { this.heap.push(num); this.bubbleUp(); } //^ 최대 요소 추출 popMax() { const max = this.heap[0]; const end = this.heap.pop(); if (this.heap.length > 0) { this.heap[0] = end; this.bubbleDown(); } return max; } getLength() { return this.heap.length; } getMax() { return this.heap[0]; } }
/* ^ 필요 자료 구조: Min heap과 Max heap ^ addNum의 로직: 1. 추가하려는 수가 현재 min heap의 .getMin()과 같거나 더 크면 min heap에 넣고, 더 작으면 max heap에 넣는다. 2. 새 수를 추가하고서 두 힙의 길이가 2 이상 차이 나면, 더 긴 쪽에서 .pop()하여 반대쪽에 넣어준다. 3. 처음엔(두 힙 모두 길이가 0이면) min heap에 넣어준다. => O(2 log N) ^ findMedian의 로직: 1. finMdeian()이 불린 시점에서 두 힙의 길이가 같으면 각각의 min과 max를 get()하여 평균을, 둘의 길이가 다르면 더 긴 쪽에서 get()한 값을 반환한다. => O(1) */ class MedianFinder { minHeap: MinHeap maxHeap: MaxHeap constructor() { this.minHeap = new MinHeap(); this.maxHeap = new MaxHeap(); } addNum(num: number) { if (num < this.minHeap.getMin()) this.maxHeap.insert(num); else this.minHeap.insert(num); // initially(when both lengths are 0), the number goes to the min heap naturally. const minLength = this.minHeap.getLength(); const maxLength = this.maxHeap.getLength(); if (minLength - maxLength >= 2) { // min heap에서 뽑아서 max heap으로 const popped = this.minHeap.popMin(); this.maxHeap.insert(popped); } if (maxLength - minLength >= 2) { // max heap에서 뽑아서 min heap으로 const popped = this.maxHeap.popMax(); this.minHeap.insert(popped); } } findMedian(): number { const minLength = this.minHeap.getLength(); const maxLength = this.maxHeap.getLength(); const min = this.minHeap.getMin(); const max = this.maxHeap.getMax(); if (minLength === maxLength) return (min + max) / 2; return (minLength > maxLength) ? min : max; } }
Uploaded by N2T