<div id="readability-page-1" class="page"><div class="page" post="">
 
 
 <hr>
 <article itemscope="" itemtype="http://schema.org/BlogPosting">
 <ul id="markdown-toc">
 <li><a href="#973-k-closest-points-to-origin" id="markdown-toc-973-k-closest-points-to-origin">973. K Closest Points to Origin</a> <ul>
 <li><a href="#problem" id="markdown-toc-problem">Problem</a></li>
 <li><a href="#example" id="markdown-toc-example">Example</a></li>
 <li><a href="#1-code-24-01-14" id="markdown-toc-1-code-24-01-14">[1] Code (24. 01. 14)</a></li>
 </ul>
 </li>
 <li><a href="#reference" id="markdown-toc-reference">Reference</a></li>
</ul>

<h2 id="973-k-closest-points-to-origin"><a href="https://leetcode.com/problems/k-closest-points-to-origin">973. K Closest Points to Origin</a></h2>

<h3 id="problem">Problem</h3>

<div><pre><code>Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).
The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).
You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).
</code></pre></div>

<hr>

<h3 id="example">Example</h3>

<div><pre><code>Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
</code></pre></div>

<hr>

<h3 id="1-code-24-01-14">[1] Code (24. 01. 14)</h3>

Retry -&gt; 다른 풀이 방법도 참고해서 학습해두자.

<div><pre><code>// Runtime: 239 ms
// Memory Usage: 51.9 MB
// Ref : https://leetcode.com/submissions/detail/1145480367
class Solution {
 public int[][] kClosest(int[][] points, int k) {
 List&lt;Node&gt; list = new LinkedList&lt;&gt;();
 
 for (int[] item : points) {
 int x = item[0];
 int y = item[1];
 int result = (int) Math.sqrt((int) Math.pow(x,2) + (int) Math.pow(y,2));
 list.add(new Node(item, (int) (Math.pow(x,2) + Math.pow(y,2))));
 }
 
 Collections.sort(list, (l1, l2) -&gt; {
 return l1.val - l2.val;
 });
 
 int[][] ans = new int[k][2];
 for (int i=0; i&lt;k; i++) {
 Node node = list.get(i);
 ans[i][0] = node.pos[0];
 ans[i][1] = node.pos[1];
 }
 return ans;
 }
 
 class Node {
 int[] pos;
 int val;
 
 public Node(int[] _pos, int _val) {
 pos = _pos;
 val = _val;
 }
 }
}
</code></pre></div>

<ul>
 <li>
 어렵지 않게 풀었다.

 그런데 더 효율적인 방법이 있으니 Reference Code를 살펴보자.
 </li>
</ul>

<hr>

<blockquote>
 Reference Code
</blockquote>

Code 1

<div><pre><code>// Runtime: 12 ms
// Memory Usage: 53.6 MB
// Ref : https://leetcode.com/submissions/detail/1145619908
class Solution {
 public int[][] kClosest(int[][] points, int k) {
 int N = points.length;
 int[] dists = new int[N];
 for (int i = 0; i &lt; N; ++i) {
 dists[i] = dist(points[i]);
 }

 Arrays.sort(dists); // [1]
 int distK = dists[k - 1]; // [2]
 int[][] ans = new int[k][2];
 int t = 0;
 for (int i = 0; i &lt; N; ++i) {
 if (dist(points[i]) &lt;= distK) { // [3]
 ans[t++] = points[i];
 }
 }

 return ans;
 }

 public int dist(int[] point) {
 return point[0] * point[0] + point[1] * point[1];
 }
}
</code></pre></div>

<ul>
 <li>[1] : 거리순으로 정렬을 한다.</li>
</ul>

<div><pre><code>arr : 5 4 3 2 1 
dists : 1 2 3 4 5
</code></pre></div>

<ul>
 <li>
 arr의 순서대로라면 0,0까지 값이 5,4,3,2,1 이지만

 dists는 정렬되어 있으므로 1,2,3,4,5 이다.
 </li>
 <li>
 [2] : distK는 정렬된 값 중 k번째로 0,0에서 멀리 떨어진 값이다.

 주의할 점은 dists는 정렬된 배열이므로

 points[i] 값과 dists[i]의 값은 다를 수 있다.
 </li>
 <li>
 [3] : dists 배열에서 0~k-1까지의 값은

 문제에서 요구한 K번째까지 0,0에 가까운 값들이다.

 그러므로 points 배열에 대해 0~N까지 순회를 돌면서

 i번째 값과 0,0까지 거리 값을 보면서

 정답이 될 수 있는 값들을 찾는다.
 </li>
</ul>

Example

<div><pre><code>arr : 15 14 13 12 11 // points[i]에서 0,0까지 거리의 값 목록들
dists : 11 12 13 14 15
k = 3
</code></pre></div>

<ul>
 <li>
 distK = 13이 되고

 arr<a href="=15">0</a> &gt; 13이므로

 k closest points 조건을 충족하지 못하므로 Pass

 arr<a href="=12">3</a> &lt; 13이므로

 k closest points 조건을 충족
 </li>
</ul>

<hr>

Code 2

<div><pre><code>// Runtime: 29 ms
// Memory Usage: 55.6 MB
// Ref : https://leetcode.com/submissions/detail/1145620299
class Solution {
 public int[][] kClosest(int[][] points, int k) {
 int [][] ans = new int [k][];
 PriorityQueue&lt;int[]&gt; pq = new PriorityQueue&lt;&gt;((p1,p2)-&gt; p2[0]*p2[0] + p2[1]*p2[1] - p1[0]*p1[0] - p1[1]*p1[1]); // [1], [2]
 for(int [] p : points){
 pq.add(p);
 if(pq.size()&gt;k)
 pq.poll();
 }
 int i=0;
 while(!pq.isEmpty()){
 ans[i++] = pq.poll();
 }
 return ans;
 }
}
</code></pre></div>

<ul>
 <li>
 [1] : PQ에 int[] 타입으로 선언할 수 있다.
 </li>
 <li>
 [2] : 값을 넣으면서 동시에 정렬 조건을 설정해 주면 쉽게 문제를 풀 수 있다.
 </li>
</ul>

<hr>

<blockquote>
 Review
</blockquote>

<ul>
 <li>
 처음엔 엄청 쉽겠네 했다가

 효율성을 고려하게 된 문제였다.
 </li>
</ul>

<hr>

<h2 id="reference">Reference</h2>

<ul>
 <li><a href="https://leetcode.com/problems/k-closest-points-to-origin">973. K Closest Points to Origin</a></li>
</ul>

 </article>
 
 <hr>

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 


<h2 id="recommend">Recommend</h2>



 </div></div>

Gidhub

973. K Closest Points to Origin 
Problem
Example
[1] Code (24. 01. 14)
Reference
973. K Closest Points to Origin
Problem
Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).
The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).
You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).
Example
Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
[1] Code (24. 01. 14)
Retry -> 다른 풀이 방법도 참고해서 학습해두자.
// Runtime: 239 ms
// Memory Usage: 51.9 MB
// Ref : https://leetcode.com/submissions/detail/1145480367
class Solution {
 public int[][] kClosest(int[][] points, int k) {
 List<Node> list = new LinkedList<>();
 
 for (int[] item : points) {
 int x = item[0];
 int y = item[1];
 int result = (int) Math.sqrt((int) Math.pow(x,2) + (int) Math.pow(y,2));
 list.add(new Node(item, (int) (Math.pow(x,2) + Math.pow(y,2))));
 }
 
 Collections.sort(list, (l1, l2) -> {
 return l1.val - l2.val;
 });
 
 int[][] ans = new int[k][2];
 for (int i=0; i<k; i++) {
 Node node = list.get(i);
 ans[i][0] = node.pos[0];
 ans[i][1] = node.pos[1];
 }
 return ans;
 }
 
 class Node {
 int[] pos;
 int val;
 
 public Node(int[] _pos, int _val) {
 pos = _pos;
 val = _val;
 }
 }
}
어렵지 않게 풀었다.
그런데 더 효율적인 방법이 있으니 Reference Code를 살펴보자.
Reference Code
Code 1
// Runtime: 12 ms
// Memory Usage: 53.6 MB
// Ref : https://leetcode.com/submissions/detail/1145619908
class Solution {
 public int[][] kClosest(int[][] points, int k) {
 int N = points.length;
 int[] dists = new int[N];
 for (int i = 0; i < N; ++i) {
 dists[i] = dist(points[i]);
 }
 Arrays.sort(dists); // [1]
 int distK = dists[k - 1]; // [2]
 int[][] ans = new int[k][2];
 int t = 0;
 for (int i = 0; i < N; ++i) {
 if (dist(points[i]) <= distK) { // [3]
 ans[t++] = points[i];
 }
 }
 return ans;
 }
 public int dist(int[] point) {
 return point[0] * point[0] + point[1] * point[1];
 }
}
[1] : 거리순으로 정렬을 한다.
arr : 5 4 3 2 1 
dists : 1 2 3 4 5
arr의 순서대로라면 0,0까지 값이 5,4,3,2,1 이지만
dists는 정렬되어 있으므로 1,2,3,4,5 이다.
[2] : distK는 정렬된 값 중 k번째로 0,0에서 멀리 떨어진 값이다.
주의할 점은 dists는 정렬된 배열이므로
points[i] 값과 dists[i]의 값은 다를 수 있다.
[3] : dists 배열에서 0~k-1까지의 값은
문제에서 요구한 K번째까지 0,0에 가까운 값들이다.
그러므로 points 배열에 대해 0~N까지 순회를 돌면서
i번째 값과 0,0까지 거리 값을 보면서
정답이 될 수 있는 값들을 찾는다.
Example
arr : 15 14 13 12 11 // points[i]에서 0,0까지 거리의 값 목록들
dists : 11 12 13 14 15
k = 3
distK = 13이 되고
arr0 > 13이므로
k closest points 조건을 충족하지 못하므로 Pass
arr3 < 13이므로
k closest points 조건을 충족
Code 2
// Runtime: 29 ms
// Memory Usage: 55.6 MB
// Ref : https://leetcode.com/submissions/detail/1145620299
class Solution {
 public int[][] kClosest(int[][] points, int k) {
 int [][] ans = new int [k][];
 PriorityQueue<int[]> pq = new PriorityQueue<>((p1,p2)-> p2[0]*p2[0] + p2[1]*p2[1] - p1[0]*p1[0] - p1[1]*p1[1]); // [1], [2]
 for(int [] p : points){
 pq.add(p);
 if(pq.size()>k)
 pq.poll();
 }
 int i=0;
 while(!pq.isEmpty()){
 ans[i++] = pq.poll();
 }
 return ans;
 }
}
[1] : PQ에 int[] 타입으로 선언할 수 있다.
[2] : 값을 넣으면서 동시에 정렬 조건을 설정해 주면 쉽게 문제를 풀 수 있다.
Review
처음엔 엄청 쉽겠네 했다가
효율성을 고려하게 된 문제였다.
Reference
973. K Closest Points to Origin

LeetCode : 973. K Closest Points to Origin

댓글