K Closest Points to Origin

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

K Closest Points to Origin - LeetCode

 

원점에서 가까운 순서대로 좌표 k 개를 찾는 문제이다. 가까운 순서대로 정렬해야 하므로 PriorityQueue를 이용하여 해결하였다.

 

PriorityQueue를 이용할 때 원하는 방식으로 정렬하기 위해선 Comparator를 지정해주거나 class가 Comparable 인터페이스를 구현하면 된다. Point에 대하여 별도의 클래스를 생성했으므로 Comparable 인터페이스를 구현해주었다.

 

원점까지의 거리는 두 점의 차이점에 제곱을 각각 한 이후 루트를 해주어야 하지만, 원점의 좌표가 0인점, 그리고 루트 계산을 해주지 않아도 크기 비교는 할 수 있다는 점에서 루트 계산은 제거하였다.

import java.util.*;  
  
public class Solution {  
    public int[][] kClosest(int[][] points, int k) {  
  
        PriorityQueue<Point> pq = new PriorityQueue<>();  
  
        for(int i = 0; i < points.length; i++){  
            int x = points[i][0];  
            int y = points[i][1];  
            pq.add(new Point(x, y));  
        }  
  
        int[][] answer = new int[k][2];  
        while(k-- > 0){  
            Point point = pq.poll();  
            answer[k][0] = point.x;  
            answer[k][1] = point.y;  
        }  
  
        return answer;  
    }  
  
    private class Point implements Comparable<Point>{  
        int x;  
        int y;  
        int distFromOrigin;  
  
        Point(int x, int y){  
            this.x = x;  
            this.y = y;  
            this.distFromOrigin = x*x + y*y;  
        }  
  
        @Override  
        public int compareTo(Point o){  
            return this.distFromOrigin - o.distFromOrigin;  
        }  
    }  
}