feat: [Med.] K Closest Points to Origin (JS/TS)

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

1. 문제분석
좌표평면 -> [x,y] 1~10,000개 points[], 정수 k -> [0,0] 기준 가장 가까운 점 부터 k개 리턴

2. 풀어보기
[[1,3],[-2,2]], 1개 -> [1^2+3^2,(-2)^2+2^2] -> [10,8] -> [1,3] 리턴

3. 슈도코드
points[] 돌려서 -> 우선순위큐에 넣는데, comparator를 거리공식 사용 (루트 생략)

4. 구현코드

type Point = [number, number];

const by_distance_asc = ([x1, y1]: Point, [x2, y2]: Point) => x1 ** 2 + y1 ** 2 < x2 ** 2 + y2 ** 2;

const kClosest = (points: Point[], k: number): Point[] => {
  if (points.length === k) {
    return points;
  }

  return by_array(points, k);
  // return by_heap(points, k);
};

const by_array = (points: Point[], k: number): Point[] => {
  points.sort((a, b) => (by_distance_asc(a, b) ? -1 : 1)); // result set의 유니크가 보장됨

  return points.slice(0, k);
};

const by_heap = (points: Point[], k: number) => {
  const result: Point[] = [];
  const heap = new Heap<Point>(by_distance_asc, points);

  for (let i = 0; i < k; i++) {
    result.push(heap.pop()!); // 문제에서 k <= points.length 보장됨
  }

  return result;
};

class Heap<T>; // 힙 구현은 https://ha2el.tistory.com/23 참고

5. 풀이회고
힙에 comparator 정의해서 입력좌표 다 넣고, k개 빼기만 하면 되는 아주 간단한 문제였다.

기본적인 문제지만, 책에도 있고 Glind75에도 있는 것 보니 핵심적인 유형인 것 같다. 항상 기본이 제일 중요하다.

그리고 나는 당연히 힙만 생각했는데, Solutions를 보니 그냥 배열 정렬해서 k개 잘라 뱉는 코드도 있었다.

실제로 돌려보니 오히려 이 쪽이 힙 보다 더 빨랐다. 오퍼레이션이 더 간단해서 그런 듯.