K Closest Points to Origin

🔗 문제 링크

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

❔ 문제 설명

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., $\sqrt{(x^1 - x^2)^2 + (y^1 - y^2)^2}$).

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

⚠️ 제한사항

• $1 <= k <= points.length <= 10^4$

• $-10^4 < xi, yi < 10^4$

---

💡 풀이 (언어 : Java)

직접 정렬 기준을 comparator를 구현해 정의하면 쉽게 풀 수 있다. 루트 안의 값들의 크기로만 비교하면 되므로 제곱근 연산은 일부러 하지 않았다. 아래는 배울만한 우선순위 큐를 이용한 풀이다.

import java.util.Arrays;

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        Arrays.sort(points, (o1, o2) -> {
            double one = Math.pow(o1[0],2)+Math.pow(o1[1],2), two = Math.pow(o2[0],2)+Math.pow(o2[1],2);
            if (one < two)
                return -1;
            else if (one > two)
                return 1;
            else
                return 0;
        });
        int[][] answer = new int[k][2];
        for (int i = 0; i < k; i++)
            answer[i] = points[i];
        return answer;
    }
}

우선순위 큐

import java.util.PriorityQueue;
import java.util.Queue;

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        // 우선 순위 기준 comparaotr를 정의한 우선순위 큐(힙)을 만들고 원소를 넣어줌
        Queue<int[]> queue = new PriorityQueue<>((a, b) -> (a[0]*a[0] + a[1]*a[1]) - (b[0]*b[0] + b[1]*b[1]));
        for (int[] p : points)
            queue.offer(p);
        int[][] answer = new int[k][2];
        for (int i = 0; i < k; i++)
            answer[i] = queue.poll();
        return answer;
    }
}