10/23 (월) (완료)스트림에서 중위값 찾기 TIL

공부한 것

LeetCode #295. 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

공부한 것

티스토리툴바