10/17 (화) 배열에서 K번째로 큰 수 찾기(최소 힙 구현) TIL

공부한 것

LeetCode #215. Kth Largest Element in an Array

⇒ 주어진 숫자 배열에서 k번째로 큰 수를 찾아 반환하는 문제. 수들은 중복으로 존재할 수 있고, sort 함수를 사용하지 말 것.

생각 과정: ‘max heap을 만들어서 k개로 자르고 맨 마지막 수를 반환하기? 안된다. 맨 앞의 수를 제외한 뒤의 수들은 크기 정렬이 안 되어 있다. 그러면 min heap을 만들어서 k개로 자르고 맨 앞의 수를 반환하자.’

1번 풀이 코드:

function findKthLargest(nums: number[], k: number): number {
	const minHeap: MinHeap = new MinHeap();
	for (const num of nums) {
		// 1. k개에 못 미치면 그냥 넣기
		// 2. k개이고 지금 넣는 수가 min보다 크거나 같으면면: min을 먼저 빼고, 지금 수를 넣기
		if (minHeap.getLength() < k)
			minHeap.insert(num);
		else if (num >= minHeap.getMin()) {
			minHeap.popMin();
			minHeap.insert(num);
		}
	}

	return minHeap.getMin(); 
};

class MinHeap {
	private heap: number[];

	constructor() {
		this.heap = [];
	}

	// heap배열의 마지막 자리에 위치한 요소를 제자리로(Heapify): bubble up
	private bubbleUp() {
		let index = this.heap.length - 1;
		let element, parentIndex, parent;

		while (index > 0) {
			element = this.heap[index]
			parentIndex = Math.floor((index - 1) / 2);
			parent = this.heap[parentIndex];
			
			if (element >= parent) break;

			this.heap[parentIndex] = element;
			this.heap[index] = parent;
			
			index = parentIndex;	
		}
	}

	// heap배열의 첫 자리에 위치한 요소를 제자리로(Heapify): bubble down
	private bubbleDown() {
		let index = 0;
		let element: number;
		let leftChildIndex: number, rightChildIndex: number;
		let leftChild: number, rightChild: number;
		let swapTarget: null | number;
		
		while (true) {
			swapTarget = null;
			element = this.heap[index];
			leftChildIndex = index * 2 + 1;
			rightChildIndex = index * 2 + 2;
			
			if (leftChildIndex < this.heap.length) {
				leftChild = this.heap[leftChildIndex];
				if (leftChild < element) {
					swapTarget = leftChildIndex;
				}
			}

			if (rightChildIndex < this.heap.length) {
				rightChild = this.heap[rightChildIndex];
				if ((swapTarget === null && rightChild < element) ||
					(swapTarget && rightChild < leftChild)) {
					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();
	}

	// 최소 요소 추출
	popMin() {
		const min = this.heap[0];
		const end = this.heap.pop();
		if (this.heap.length > 0) {
			this.heap[0] = end;
			this.bubbleDown();
		}
		return min;
	}

	getMin() {
		return this.heap[0];
	}

	getLength() {
		return this.heap.length;
	}
}

2번 풀이 코드:

function findKthLargest2(nums: number[], k: number): number {
	nums.sort((a, b) => b - a); // 내림차순 정렬
	return nums[k - 1];
}

실행 결과:

⇒ sort 메소드를 이용한 풀이 2번과 굳이 비교해보니, Min Heap을 이용하는 풀이 1번이 조금 더 빠름을 알 수 있다. sort()는 시간복잡도가 O( $NlogN$ )이고, Heap은 숫자가 들어올 때마다 logN을 진행해야 하므로 O( $log(N!)$ )이 된다. 두 함수의 크기를 비교하면 다음과 같다:

엄청난 차이는 없지만 NlogN 쪽이 더 오랜 시간이 걸린다는 것을 알 수 있다. Min Heap을 이용하는 쪽이 조금 더 빠르며, ‘현재 최소값보다 더 작은 수가 들어올 때는 해당 logN 과정을 생략’할 수도 있음을 생각해볼 때 조금 더 차이가 발생하게 된다. 그래서 위와 같은 실행 시간 차이가 발생하게 된 것이다.

최소 힙(Min Heap)을 스스로 구현해 보았다. 어제 기억이 살아 있어서 수월했다.

Uploaded by N2T

공부한 것

티스토리툴바