[LeetCode#973] K Closest Points to Origin

❒ Description

---

제목	K Closest Points to Origin
링크	https://leetcode.com/problems/k-closest-points-to-origin/description/
자료구조	선형 (우선순위 큐)
시간복잡도	O(nlogn)

 

이번 문제는 우선순위 큐를 사용하여 해결하는 문제이다. Sort, Heap, Quick Select를 사용하는

구현도 있는데 이것에 대해서는 해당 섹션 공부할 때 같이 볼 예정이다.

 

이 문제는 Comparator와 Comparable 중 하나를 사용해서 우선순위를 결정해줘야 한다.

Comparator를 통해서 우선순위를 정해줄 경우 main method에서 `Comparator#compare`메서드를

제정의 해줘야해서 DDD에 어긋난다.

 

반면에 Comparable를 사용하게 되면 Point 클래스가 Comparable 인터페이스를 implement하면 되기 

때문에 Point 도메인이 우선순위 결정하는 로직을 갖고 있게 된다. 이렇게 하면 재사용할 및 수정에 장점을

가져갈 수 있게 된다. 또한 메서들 명(calculateDistanceUsing)을 굉장히 직관적으로 작성할 수 있다.

 

 

 

❒ Solution

---

1. Comparator

1-1. Point 중첩 클래스

public static class Point {
    long distance;
    int[] point;

    public Point(long distance, int[] point) {
        this.distance = distance;
        this.point = point;
    }
}

 

1-2. main method

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

    Comparator<Point> pointComp = new Comparator<Point>() {
        @Override
        public int compare(Point o1, Point o2) {
            if (o1.distance == o2.distance) {
                return 0;
            } else if (o1.distance > o2.distance) {
                return 1;
            } else {
                return -1;
            }
        }
    };

    PriorityQueue<Point> pointPQ = new PriorityQueue<>(pointComp);

    for(int[] point : points) {
        pointPQ.add(new Point(calculateDistance(point), point));
    }

    int[][] result = new int[k][2];
    for(int i = 0; i < k; i++) {
        Point target = pointPQ.poll();
        result[i] = target.point;
    }

    return result;
}

private Long calculateDistance(int[] point) {
    return ((long) point[0] * point[0]) + ((long) point[1] * point[1]);
}

 

---

 

2. Comparable

2-1. Point inner 클래스

public static class Point implements Comparable<Point> {
    long distance;
    int[] point;

    public Point(long distance, int[] point) {
        this.distance = distance;
        this.point = point;
    }

    public Point(int[] point) {
        this.distance = calculateDistanceUsing(point);
        this.point = point;
    }

    private long calculateDistanceUsing(int[] point) {
        return (long) (point[0] * point[0]) + (long) (point[1] * point[1]);
    }

    @Override
    public int compareTo(Point other) {
        return Long.compare(this.distance, other.distance);
    }
}

 

2-2. main method

public int[][] kClosest(int[][] points, int k) {
    PriorityQueue<Point> pq = new PriorityQueue<>();

    for (int[] point : points) {
        pq.add(new Point(point));
    }

    int[][] result = new int[k][2];
    for (int i = 0; i < k; i++) {
        Point target = pq.poll();
        result[i] = target.point;
    }
    return result;
}