[JAVA][Array] KClosestPointstoOrigin

1. 문제

We have a list of points on the plane.
Find the K closest points to the origin (0, 0).
(Here, the distance between two points on a plane is the Euclidean distance.)
You may return the answer in any order.
The answer is guaranteed to be unique (except for the order that it is in.)
Example 1:
Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Explanation: The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin. We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].

 

2. 문제해설

input으로 point를 주는데 그 중 0,0에서 K개수 만큼 가까운 지점의 좌표를 구하라

 

3. 코드포맷

class Interval {
	int start;
	int end;

	Interval() {
		this.start = 0;
		this.end = 0;
	}

	Interval(int s, int e) {
		this.start = s;
		this.end = e;
	}

	@Override
	public String toString() {
		return start + ", "+end;
	}
	
}

public class KClosestPointstoOrigin {
	public static void main(String[] args) {
		List<Interval> list = new ArrayList<Interval>();
		Interval in1 = new Interval(1, 3);
		Interval in2 = new Interval(-2, 2);
		Interval in3 = new Interval(-1, 2);
		list.add(in1);
		list.add(in2);
		list.add(in3);
		kClosest(list, 2);
	}
}

 

4. 접근 방법

각각의 좌표를 0~가로좌표, 0~세로좌표의 제곱하고 더한값의 가장 작은 수를 구한다.

 

5. 코드

public class KClosestPointstoOrigin {
	public static void main(String[] args) {
		List<Interval> list = new ArrayList<Interval>();
		Interval in1 = new Interval(1, 3);
		Interval in2 = new Interval(-2, 2);
		Interval in3 = new Interval(-1, 2);
		list.add(in1);
		list.add(in2);
		list.add(in3);
		kClosest(list, 2);
	}

	private static void kClosest(List<Interval> list, int i) {
		//일반적인 큐가 아니라 우선순위 정렬 큐를 사용함
        //큐가 아니라 list에서 바로 정렬하여도 됨
		Queue<Interval> q = new PriorityQueue<Interval>(comp);
		for(Interval in :list) {
			q.add(in);
		}
		for(int index =0;index<i;index++) {
			System.out.println(q.poll());
		}
	}
	
	static Comparator<Interval> comp = new Comparator<Interval>() {
		@Override
		public int compare(Interval o1, Interval o2) {
			int fir = (int) (Math.pow(o1.start,2)+Math.pow(o1.end, 2));
			int sec = (int) (Math.pow(o2.start,2)+Math.pow(o2.end, 2));
			return fir-sec;
		}
	};
}