[LeetCode- Ch.2 정렬 & 검색] 3. 원점에 가장 가까운 지점 ## (+ Double 정렬, PriorityQueue 정렬)

 

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

K Closest Points to Origin - LeetCode

 

 

1. 제곱근 함수 : Math.sqrt()

2. 제곱 함수    : Math.pow()

 

import java.util.*;
class Point{
    public double value;
    public int[] arr;
    Point(double value, int[]arr){
        this.value=value;
        this.arr=arr;
    }
}
class Solution {
    public int[][] kClosest(int[][] points, int k) {
        //한 점에서 원점까지 가장 가까운 K개 좌표 리턴
        int n=points.length;
        double[] arr = new double[n];
        for(int i=0;i<n;i++){
            arr[i] = 
    Math.sqrt(Math.pow((double)points[i][0],2)+Math.pow((double)points[i][1],2));
        }
        
        ArrayList<Point> list = new ArrayList<>();
        
        for(int i=0;i<n;i++){
            list.add(new Point(arr[i],points[i]));
        }
        int[][] answer=new int[k][2];
        list.sort(new Comparator<Point>(){
            @Override
            public int compare(Point o1, Point o2){
                //내림차순
                if(o1.value>o2.value)
                return 1;
                else return -1;
            }
        });
        for(int i=0;i<k;i++){
            answer[i]=list.get(i).arr;
        }
        
        return answer;
    }
}

 

+) 세련된 코드

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        // 1. ds
		Queue<int[]> pq = new PriorityQueue<>((a, b) -> (a[0] * a[0] + a[1] * a[1]) - (b[0] * b[0] + b[1] * b[1]));
		int[][] result = new int[k][2];

		// 2. for, while
		for (int[] p : points) {
			pq.offer(p);
		}
		int index = 0;
		while (index < k) {
			result[index++] = pq.poll();
		}
		return result;
	}
}

 

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        // 1. ds
		Queue<int[]> pq = new PriorityQueue<>((a, b) -> (a[0] * a[0] + a[1] * a[1]) - (b[0] * b[0] + b[1] * b[1]));
		int[][] result = new int[k][2];

		// 2. for, while
		for (int[] p : points) {
			pq.offer(p);
		}
		int index = 0;
		while (index < k) {
			result[index] = pq.poll();
			index++;
		}
		return result;
	}
}

---

import java.util.*;
class Point{
    public int x, y;
    double value;
    Point(int x, int y, double value){
        this.x=x;
        this.y=y;
        this.value=value;
    }
    
}
class Solution {
    public int[][] kClosest(int[][] points, int k) {
        int[][] answer= new int[k][2];
        int n=points.length;
        // if(o1.value>o2.value)
                //return 1;
                //else return -1;
     PriorityQueue<Point> q = new PriorityQueue<Point>((Point p1, Point p2) -> p1.value>p2.value?1:-1);        
        for(int i=0;i<n; i++){
            int x=points[i][0];
            int y=points[i][1];
q.offer(new Point(x,y,Math.sqrt(Math.pow((double)x,2)+Math.pow((double)y,2))));
        }
   
        int index=0;
        while(!q.isEmpty() && k>0){
            k--;
            Point point=q.poll();
            answer[index][0]=point.x;
            answer[index][1]=point.y;
            index++;
            if(k==0) return answer;
        }
        return answer;
    }
}

---

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        int n=points.length;
        int[][] answer= new int[k][2];
        Queue<int[]> q = new PriorityQueue<>((o1,o2)-> (o1[0]*o1[0]+o1[1]*o1[1])-(o2[0]*o2[0]+o2[1]*o2[1]));
        for(int i=0;i<n;i++){
            q.offer(points[i]);     
        }
        for(int i=0;i<k; i++){
            answer[i]=q.poll();
        }
        
        return answer;
    }
}