K Closest Points to Origin

We have a list of points on the plane. Find the K closest points to the origin (0,0).

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order. The answer is guaranteed to be unique(except for the order that it is in.)

평판 위의 points 리스트를 갖고 있다. 원점에서 가장 가까운 K 개의 points 를 찾아라.

(여기서 두 점 사이의 거리는 유클리드의 거리이다.)

순서상관없이 정답을 리턴할 수 있다. 정답은 유일무이함을 보장한다.(순서 제외)

Example 1: Input : points =[ [1,3], [-2,2] ], K = 1 Output : [ [-2,2] ]

Example 2: Input : points = [ [3,3], [5,-1], [-2,4] ], K = 2 Output : [ [3,3], [-2,4] ]//[ [-2,4], [3,3] ] 도 정답 가능

1. 1 <= K <= points.length <= 10000

2. -10000 < points[ i ][ 0 ] < 10000

3. -10000 < points[ i ][ 1 ] < 10000

1. 담을 그릇 정한다. - List 이용 2. 알고리즘

class point {//문제에서 point 클래스가 주어지겠지.
    int x;
    int y;
    point(int pointX, int pointY) { x = pointX; y = pointY;}
}

알고리즘 #1. 우선순위 큐 이용

1. 담을 그릇 정한다. - 우선순위 큐와 정답 담을 2차원 배열

2. 큐에 데이터 넣는다.

3. 정답 배열에 데이터 넣는다.

class Solution {
    public int[][] kClosest(int[][] points, int K) {
        //1.담을 그릇 생성
        Queue<int[]> queue = new PriorityQueue<int[]>(points.length,Comp);
        int[][] result = new int[K][2];
        int index=0;
        //2.큐에 데이터 삽입
        for(int[] p : points) {
            queue.offer(p);
        }
        //3.result에 큐로부터 데이터 저장
        while(index < K) {//for반복문을 while문으로 나타냈다고 생각
            result[index] = queue.poll();
            index++;
        }
        return result;
        
        
    }
    Comparator<int[]> Comp = new Comparator<int[]>(){
            public int compare(int[] a, int[] b) {
                return (a[0]*a[0] + a[1]*a[1])-(b[0]*b[0] + b[1]*b[1]);
            }
        };
}

배운 내용 정리

1. 우선순위 큐 일반적으로 큐는 데이터를 일시적으로 쌓아두기 위한 자료구조로 FIFO의 구조이다. 하지만 우선순위 큐(PriorityQueue)는 우선순위(PriorityQueue)를 먼저 결정하고 그 우선순위가 높은 원소가 먼저 나가는 자료구조이다. 우선순위는 주로 힙을 이용하여 구현된다. 데이터를 삽입할 때 우선순위를 기준으로 최대힙 또는 최소힙을 구성하고, 데이터를 꺼낼 때 루트 노드를 얻는다. 루트 노드랄 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입하고 아래로 내려가면서 위치가 조정된다.