973. K Closest Points to Origin

문제

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

풀이

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>((a,b) -> {
            int prior = points[a][0] * points[a][0] + points[a][1] * points[a][1];
            int later = points[b][0] * points[b][0] + points[b][1] * points[b][1];
            return prior - later;
            });

        int[][] kClosest = new int[k][2];

        for(int i = 0; i < points.length; i++) {
            heap.add(i);
        }

        for(int i = 0; i < k; i++) {
            int index = heap.poll();
            kClosest[i] = points[index];
        }

        return kClosest;
    }
}

• (0,0)까지의 거리가 가장 가까운 순서대로 k번 만큼 꺼내주면 됨
  • 우선순위 큐에 넣고, x^2 + y^2의 값이 가장 작은 순서부터 꺼내주면 된다.

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        PriorityQueue<int[]> heap = new PriorityQueue<>((a,b) -> {
            int prior = a[0] * a[0] + a[1] * a[1];
            int later = b[0] * b[0] + b[1] * b[1];
            return prior - later;
            });

        int[][] kClosest = new int[k][2];

        for(int i = 0; i < points.length; i++) {
            heap.add(points[i]);
        }

        for(int i = 0; i < k; i++) {
            int[] arr = heap.poll();
            kClosest[i] = arr;
        }

        return kClosest;
    }
}

• 이렇게 배열을 우선순위큐에 넣을 수도 있음