LeetCode - K closest point to origin

문제 소개

좌표가 담긴 배열과 K 값이 주어진다.
원점에서 가까운 좌표 순대로 K개를 뽑아 배열로 리턴하라.

방법

일단 Priority Queue 문제라는 생각이 들었다.
시간복잡도는 $O(n*log_2 N)$ 이라는 생각이 들었고
Point를 Comparable 하게 만들어서 Priority Queue로 만들어 주면 쉽게 풀 수 있지 않을까 하는 생각이 들었다.

코드

import java.util.*;
class Solution {
    public int[][] kClosest(int[][] points, int K) {
        PriorityQueue<Point> queue = new PriorityQueue<>();
        
        for(int i=0; i<points.length; i++)
            queue.add(new Point(points[i][0],points[i][1]));
        
        int[][] answer = new int[K][2];
        
        for(int i=0; i<K; i++){
            Point p = queue.poll();
            answer[i][0] = p.x;
            answer[i][1] = p.y;
        }
        
        return answer;
    }
}

class Point implements Comparable<Point>{
    public int x;
    public int y;
    public int distance;
    
    public Point(int x,int y){
        this.x = x;
        this.y = y;
        this.distance = x*x + y*y;
    }
    
    @Override
    public int compareTo(Point other){
        return Integer.compare(distance,other.distance);
    }
}

해결

한 10분 정도 걸린 것 같다.

앞으로도 문제를 보면 어떤 방식으로 접근해야할지 많이 떠올랐으면 좋겠다

• 끗 -