973. K Closest Points to Origin

• 며칠전 풀었던 문제와 비슷하게, closest K 가 조건인 만큼, PQ 를 이용하면  될것 같아서 접근했고, compile 에러 ( pq.size() 에서 () 빼먹음, cnt++;  에서 ; 빼먹음)  을 빼면 한번에 accept 되었다.
•  closest K 를 구하는 만큼, max heap 을 이용하는 것이 포인트 이다. 
• time complexity 는 PQ 에 point  개수 N 개 만큼 insert 했으므로, O(NlogN) 이 되는것 같다.
• 하지만 내 풀이는 28ms 로, 매우 오래 걸렸다.

• 다시 보니, 전체 points  를 모조리 정렬하지 않았으므로  O(NlogN)이 아닌, O(NlogK) 가 된다. K 개의 PQ  를 관리 하였기 때문이다.
• 어떤이가 Top K 접근법에 대해 잘 정리해둔 글이 있어, 요약한다.

Top K 접근법

1. 정렬이다. 모조리 정렬 후  K 개를 찾는 것으로, 

• 직관적이고 코드 길이가 매우 짧다
• 하지만 매우 비효율적이며, 이미 나온 앞의 항목들도 모조리 들고 있어야 한다는 점,으로  real-time 에서는 사용할 수 없다.
• O(NlogN) 이 된다.

2.  Max Heap with K size 를 이용한다. 내가 한 방법으로,

• real-time online (stream)  데이터에서도 적용 가능하고, 이전의 데이터 사이즈에 대해 알 필요가 없는것이 장점이다.
• 가장 효율적인 솔루션은 아니다.(!)
• 이론적으로 O(NlogK) 가 된다.

3. QuickSelect 를 이용한다. 들어는 본 적이 있는 방법으로,

• QuickSort 와 비슷하게, pivot 을 정해서, pivot 보다 크면 오른쪽으로, 작으면 왼쪽으로 몰아 넣고 pivot 이 들어갈 자리를 찾는 방식이다.
• QuickSort 는 Average O(NlogN), Worst O(N^2) 의 복잡도를 갖지만,
• QuickSelect  는 top K 개를 찾으므로,  pivot 의  한쪽에만 관심이 있다.
• 이론적으로, QuickSelect 는 Average O(N), Worst O(N^2) 이다.
• 장점으로는 3개 방법중 제일 효율적이지만
• Worst 인 경우 N^2 라는 점, K 개의 결과가 정렬되지는 않는다는 점이 있다.

QuickSelect 는 한번 봐서 이해는 안되고, 계속 봐야 할것 같다.

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];
}

참조 https://leetcode.com/problems/k-closest-points-to-origin/discuss/220235/Java-Three-solutions-to-this-classical-K-th-problem.