[LeetCode/MEDIUM] 973. K Closest Points to Origin (JAVA) : 문제&풀이

 

 

원점과 가까운 상위 k개의 점을 구하는 문제이다.

 

2차원 int 배열과 int를 매개변수로 받는 kClosest 메서드의 틀이 주어진다.

 

Problem :

public class KClosestPointToOrigin {
    public int[][] kClosest(int[][] points, int k) {
        return result;
    }
}

풀이는 kClosest 메서드에 작성하면 된다.

 

Solution :

피타고라스의 정리에 따라 좌표평면에서 두 점 사이의 거리를 구하는 공식은 다음과 같다.

이 때, 두 점 중 하나는 원점이므로, 식은 다음과 같이 간략화 할 수 있다.

본 풀이에서는 거리 순위에 영향을 주지 않으면서 계산을 더욱 간소화 하기 위해 제곱근을 제외하고 비교했다.

1. 앞서 설명한 간소화된 원점과의 거리비교 계산식을 우선순위 기준으로 하는 PriorityQueue를 생성한다.
   (두 개의 제곱근을 제외한 원점과의 거리 계산식 결과를 오름차순으로 한다.)
2. 반복문을 돌며 생성한 PriorityQueue에 좌표들을 넣는다.
3. 주어진 k개 만큼 PriorityQueue에서 뽑아 반환한다. (오름차순 정렬이므로 상위 k개)

import java.util.PriorityQueue;

public class KClosestPointToOrigin {

    // time complexity : priorityQueue sort -> O(n log n)
    // space complexity : PriorityQueue<int[]> -> O(n)
    public int[][] kClosest(int[][] points, int k) {

        // PriorityQueue based on distance calc (min-heap)
        PriorityQueue<int[]> distancePQueue = new PriorityQueue<>((a, b) -> ((a[0]*a[0] + a[1]*a[1]) - (b[0]*b[0] + b[1]*b[1]))); // ASC
        for (int[] point : points) {
            distancePQueue.offer(point);
        }

        // get k amount
        int[][] result = new int[k][2];
        while (k > 0) {
            result[--k] = distancePQueue.poll();
        }

        return result;
    }
}

 

 

Complexity :

• 시간복잡도 (Time Complexity)
  • PriorityQueue sort에 따라 O(n log n)
• 공간복잡도 (Space Complexity)
  • 매개변수 points만큼 담아둘 PriorityQueue사용에 따라 O(n)

 

Sample(Test) :

import java.util.Arrays;
import java.util.PriorityQueue;

public class KClosestPointToOrigin {

    // time complexity : priorityQueue sort -> O(n log n)
    // space complexity : PriorityQueue<int[]> -> O(n)
    public int[][] kClosest(int[][] points, int k) {

        // PriorityQueue based on distance calc (min-heap)
        PriorityQueue<int[]> distancePQueue = new PriorityQueue<>((a, b) -> ((a[0]*a[0] + a[1]*a[1]) - (b[0]*b[0] + b[1]*b[1]))); // ASC
        for (int[] point : points) {
            distancePQueue.offer(point);
        }

        // get k amount
        int[][] result = new int[k][2];
        while (k > 0) {
            result[--k] = distancePQueue.poll();
        }

        return result;
    }

    public static void main(String[] args) {
        int[][] points = new int[][]{{3, 3}, {5, -1}, {-2, 4}};
        int k = 2;

        KClosestPointToOrigin kc = new KClosestPointToOrigin();
        for (int[] point : kc.kClosest(points, k)) {
            System.out.println(Arrays.toString(point));
        }
    }
}

 

위 테스트 코드를 실행한 결과는 다음과 같다.

[-2, 4]
[3, 3]