[Medium] 973. K Closest Points to Origin (Facebook / Meta)

#문제 설명

Leetcode 973번 문제는 x, y축 위의 좌표들이 배열로 주어지고, 정수 k가 주어진다. 이 문제에서는 (0,0) 에 가장 가까운 좌표 k개를 포함한 array를 return하는 문제이다.

#문제 풀이

#풀이 1

class Solution{
public int[][] kClosest(int[][] points, int K) {
    Arrays.sort(points, (p1, p2) -> p1[0] * p1[0] + p1[1] * p1[1] - p2[0] * p2[0] - p2[1] * p2[1]);
    return Arrays.copyOfRange(points, 0, K);
	}
}

모든 점을 원점까지의 거리에 따라 정렬한 다음 가장 가까운 상위 k개의 점을 얻는 풀이 이다. Time complexity는 O(nlogn) 이다. 이 풀이의 단점은 효율적이지 않고 모든 포인트를 미리 알아야 하며 실시간(online) 사례를 처리할 수 없는 off-line 풀이 이다.

 

#풀이 2

class Solution{
public int[][] kClosest(int[][] points, int K) {
    PriorityQueue<int[]> pq = new PriorityQueue<int[]>((p1, p2) -> p2[0] * p2[0] + p2[1] * p2[1] - p1[0] * p1[0] - p1[1] * p1[1]);
    for (int[] p : points) {
        pq.offer(p);
        if (pq.size() > K) {
            pq.poll();
        }
    }
    int[][] res = new int[K][2];
    while (K > 0) {
        res[--K] = pq.poll();
    }
    return res;
    }
}

두 번째 풀이는 첫 번째 풀이를 기반으로 한다. 이 풀이에서는 모든 점을 분류할 필요는 없다. 대신, K 사이즈로 max-heap을 유지한다. 그런 다음 각 좌표를 힙에 추가한다. 일단 힙의 크기가 K보다 크면, 힙의 크기가 항상 K가 되도록 하기 위해 최대 힙 (max-heap)에서 하나의 좌표를 추출해야 한다. 따라서, 최대 힙은 항상 첫 번째 element부터 현재 element까지 상위 K개의 가장 작은 element를 유지한다. 힙의 크기가 최대 용량을 초과하면 힙에서 가장큰 값이 제외됨 (그 값은 더이상 정답 배열에 들어갈수 없기 때문). 이 풀이의 time complexity는 O(NlogK)이다. 여기서 K는 max-heap의 사이즈이다.

 

이 풀이의 장점은 실시간(online) 스트림 데이터를 처리할 수 있다는 것이다. 그렇기 때문에 데이터의 크기를 미리 알 필요가 없다. 이 풀이의 단점은 most-optimal (most efficient / 가장 효율적인) 풀이는 아니라는 것이다.

 

#풀이 3

class Solution{
public int[][] kClosest(int[][] points, int K) {
    int len =  points.length, l = 0, r = len - 1;
    while (l <= r) {
        int mid = helper(points, l, r);
        if (mid == K) break;
        if (mid < K) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return Arrays.copyOfRange(points, 0, K);
}

private int helper(int[][] A, int l, int r) {
    int[] pivot = A[l];
    while (l < r) {
        while (l < r && compare(A[r], pivot) >= 0) r--;
        A[l] = A[r];
        while (l < r && compare(A[l], pivot) <= 0) l++;
        A[r] = A[l];
    }
    A[l] = pivot;
    return l;
}

private int compare(int[] p1, int[] p2) {
    return p1[0] * p1[0] + p1[1] * p1[1] - p2[0] * p2[0] - p2[1] * p2[1];
    }
}

마지막 솔루션은 quick sort을 기반으로 하며,quick select이라고 불린다. quick sort에서는 항상 다른 element와 비교할 pivot (중심축)을 선택한다. 한 번 반복하면 pivot 보다 작은 모든 element가 pivot 의 왼쪽에 있고 pivot 보다 큰 모든 element들이 pivot의 오른쪽에 있는 배열을 얻을 수 있다(배열을 오름차순으로 정렬한다고 가정). 이를 기반으로 각 반복마다 pivot 을 선택하고 pivot 이 있어야 할 위치 p를 찾는다. 그런 다음 p를 K와 비교하는데, 만약 p가 K보다 작다면, pivot 의 왼쪽에 있는 모든 요소들이 모두 적절한 elemet들이지만, 오른쪽에서도 같은 작업을 수행해야한다. 만약 p가 K와 정확히 같다면,  K번째 위치를 찾았다는 것을 의미한다. 따라서 첫 번째 K 요소는 pivot보다 크지 않기 때문에 pivot을 return한다.

 

이 풀이의 time complexity는 O(n)이기때문에 가장 효율적인 풀이라고 볼수있다, 하지만 이 풀이의 단점은 online 풀이도 아니고 안정적(stable)인 솔루션도 아니다. 그리고 가장 가까운 K element는 오름차순으로 정렬되지 않는다.

#풀이 4

class Solution {
    public int[][] kClosest(int[][] points, int k) {

        int[][] distance = new int[points.length][];

          PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); 

        for(int i = 0; i < points.length; i++){
            maxHeap.add(points[i][0] * points[i][0] + 
                          points[i][1] * points[i][1]);
            if(maxHeap.size() > k){
                maxHeap.poll();
            }
        }    
            int[][] result = new int[k][];
            //int index = k - 1;
            int index = 0;
            for(int i = 0; i < points.length;i++){
                if(maxHeap.peek() >= points[i][0] * points[i][0] + 
                          points[i][1] * points[i][1]){
                              result[index++] = points[i];
                          }
            }

        return result;
    }
}

Maximum heap을 사용한 풀이이다.

#풀이 5

class Solution {
    public int[][] kClosest(int[][] points, int K) {
        int N = points.length;
        int[] dists = new int[N];
        for (int i = 0; i < N; ++i)
            dists[i] = dist(points[i]);

        Arrays.sort(dists);
        int distK = dists[K-1];

        int[][] ans = new int[K][2];
        int t = 0;
        for (int i = 0; i < N; ++i)
            if (dist(points[i]) <= distK)
                ans[t++] = points[i];
        return ans;
    }

    public int dist(int[] point) {
        return point[0] * point[0] + point[1] * point[1];
    }
}