[자바 알고리즘 인터뷰] ch 10. 데크, 우선순위 큐 (3) - 원점에서 가장 가까운 k개의 점

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

 

 

- 평면상에 points 목록이 있을 때, 원점(0,0)에서 가장 가까운 k개의 점 목록을 순서대로 출력하라. 평면상에 있는 두 점의 거리는 유클리드 거리(Euclidean Distance)로 한다. 

 

 

풀이 1) 유클리드 거리의 우선순위 큐 순서 

 

- 유클리드 거리는 두 점의 직선 거리를 의미한다. 

- 유클리드 거리를 계산하고 이 값을 우선순위 큐로 k번 출력하면 쉽게 문제를 풀 수 있다. 

 

출처 : 자바 알고리즘 인터뷰 with 코틀린 저자:박상길 <책만>

 

 

- 위의 유클리드 거리를 계산하고 이 값을 우선순위 큐에 삽입하는 코드는 다음과 같다. 

//Point 클래스를 저장하는 우선순위 큐로, 정렬 기준은 distance로 한다. 
PriorityQueue<Point> pq = new PriorityQueue<>(Comparator.comparingDouble(a->a.distance));


//파라미터로 받은 좌표 목록 순회 
for(int point[] : points)
{
    //유클리드 거리 계산
    double distance = Math.sqrt((long)point[0]*point[0] + (long)point[1]*point[1]);
    //우선순위 큐에 거리와 좌표를 Point 클래스로 담아 삽입
    pq.add(new Point(distance,point));
}

 

- 자바의 우선순위 큐는 최소 힙이므로, 디폴트로 가장 가까운 순으로 추출할 수 있다. 

- 그러나 여기서는 좌표 정보도 함께 저장할 것이기 때문에 기준 a->a.distance()라는 것을 구체적으로 명시했다. 

 

- 거리와 좌표를 함께 보관할 Point라는 이름의 클래스를 선언했고, 우선순위 큐에는 이 값을 그대로 저장했다. 

- 정렬은 distance로 하였다. 

static class Point {
    double distance; //거리
    int point[]; //좌표

    //거리와 좌표를 파라미터로 받는다.
    public Point(double distance, int point[])
    {
        this.distance = distance;
        this.point = point;
    }
}

 

 

- 결과 변수에는 우선순위 큐에서 추출한 Point 클래스에서 좌표(Point)만 추출해 k번 삽입했다. 

int results[][] = new int[k][];
//k번만큼 반복하여 결과 추출
for(int i=0; i<k; i++)
{
    //우선순위 큐에서 추출한 Point 클래스의 좌표(Point)를 결과로 삽입
    results[i] = pq.poll().point;
}

return results;

 

 

 

class Solution {
    static class Point {
        double distance; //거리
        int point[]; //좌표

        //거리와 좌표를 파라미터로 받는다.
        public Point(double distance, int point[])
        {
            this.distance = distance;
            this.point = point;
        }
    }

    public int[][] kClosest(int[][] points, int k) {
        //Point 클래스를 저장하는 우선순위 큐로, 정렬 기준은 distance로 한다. 
        PriorityQueue<Point> pq = new PriorityQueue<>(Comparator.comparingDouble(a->a.distance));


        //파라미터로 받은 좌표 목록 순회 
        for(int point[] : points)
        {
            //유클리드 거리 계산
            double distance = Math.sqrt((long)point[0]*point[0] + (long)point[1]*point[1]);
            //우선순위 큐에 거리와 좌표를 Point 클래스로 담아 삽입
            pq.add(new Point(distance,point));
        }

        int results[][] = new int[k][];
        //k번만큼 반복하여 결과 추출
        for(int i=0; i<k; i++)
        {
            //우선순위 큐에서 추출한 Point 클래스의 좌표(Point)를 결과로 삽입
            results[i] = pq.poll().point;
        }

        return results;
     }
}

28밀리초 

 

 

풀이 2) 유클리드 거리 개선 

 

- 순서만 동일하면 되므로 공식을 좀 더 간략하게 만들 수 있다. 

 

//유클리드 거리 계산
long distance = (long)point[0]*point[0] + (long)point[1]*point[1];