10/19 (목) 원점에 가장 가까운 K개의 점 TIL

공부한 것

• LeetCode #973. K Closest Points to Origin

  LeetCode - The World's Leading Online Programming Learning Platform

  Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

  https://leetcode.com/problems/k-closest-points-to-origin/description/

  

  ⇒ 좌표 평면에 흩어져 있는 점들의 위치[x,y]가 주어졌을 때 원점에 가장 가까운 k개의 점들을 따로 모아 반환하는 문제였다. Map Heap의 크기를 k로 고정시켜두면, 최종적으로 전체 점들 중 k번째 최소값보다 작은 값들만 남게 되는 원리를 이용하였다.

  • 풀이 1: Max Heap이용, 시간복잡도 O($log(N!)$)

    function kClosest(points: number[][], k: number): number[][] {
    	const maxHeap: MaxHeap = new MaxHeap();
    	for (let point of points) {
    		const [x, y] = point;
    		const distance = x * x + y * y;
    		if (maxHeap.getLength() < k) 
    			maxHeap.insert(x, y);
    		else if (maxHeap.getMax().distance > distance) {
    			maxHeap.popMax();
    			maxHeap.insert(x, y);
    		}
    	}
    
    	return maxHeap.getPositionArray();
    };
    
    interface point {
    	position: [number, number];
    	distance: number;
    }
    
    class MaxHeap {
    	private heap: point[];
    
    	constructor() {
    		this.heap = [];
    	}
    
    	// 마지막 요소를 제자리로 끌어 올리기
    	private bubbleUp() {
    		// 부모의 '거리'값보다 더 크면 부모와 자리를 교체하기를 반복한다.
    		let index = this.heap.length - 1;
    		const point = this.heap[index];
    		
    		while (index > 0) {
    			let parentIndex = Math.floor((index - 1) / 2);
    			let parent = this.heap[parentIndex];
    
    			if (point.distance <= parent.distance) break;
    
    			this.heap[parentIndex] = point;
    			this.heap[index] = parent;
    
    			index = parentIndex;
    		}
    	}
    
    	// 첫 번째 요소를 제자리로 끌어내리기
    	private bubbleDown() {
    		// 존재하는 자식 중 나의 '거리'값보다 더 큰 최대 자식과 자리를 교체하기를 반복한다. 
    		let index = 0;
    		const point = 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 (leftChild.distance > point.distance) {
    					swapTarget = leftChildIndex;
    				}
    			}
    			if (rightChildIndex < this.heap.length) {
    				rightChild = this.heap[rightChildIndex];
    				if ((swapTarget === null && rightChild.distance > point.distance) || 
    					(swapTarget !== null && rightChild.distance > leftChild.distance)) {
    					swapTarget = rightChildIndex;
    				}
    			}
    
    			if (swapTarget === null) break;
    
    			this.heap[index] = this.heap[swapTarget];
    			this.heap[swapTarget] = point;
    
    			index = swapTarget;
    		}
    	}
    
    	insert(x:number, y:number) {
    		const point: point = { distance: x * x + y * y, position: [x, y] };
    		this.heap.push(point);
    		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; 
    	}
    
    	getMax() {
    		return this.heap[0];
    	}
    
    	getLength() {
    		return this.heap.length;
    	}
    
    	getPositionArray() {
    		return this.heap.map((point) => point.position);
    	}
    }

  • 풀이 2: sort() 이용, 시간복잡도 O($N log(N)$)

    function kClosest(points: number[][], k: number): number[][] {
    	return points.map((point) => {
    		const [x, y] = point;
    		const distance: number = x * x + y * y;
    		return { position: point, distance };
    	})
    		.sort((a, b) => a.distance - b.distance)
    		.slice(0, k)
    		.map((point) => point.position);
    }

  

  위 그래프에서 보는 바와 같이 $log(N!)$이 조금 더 빨라야 하는데, 실행 결과를 보면 이번엔 그렇지만도 않다.

  

  • 최대 힙(Max Heap)에 단순 숫자(number)가 아닌 객체를 넣도록 변형한 부분이 재밌었다. 오늘로 4일째 매일 힙 구현중인데 좀 외워졌을까?

Uploaded by N2T