<aside> 👉🏿 문제 링크

</aside>

문제 정리

<aside> 👉🏿 점들의 좌표 x1,y1이 주어지고, 원점과 가까운 k개의 point들을 반환하는 문제이다.

</aside>

# 예시
Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]

접근 방법

<aside> 👉🏿 우선 이 문제는 피타고라스의 정의인 x2 + y2 = 직선의 거리를 사용한다.

위 계산한 거리를 heap에 넣고 배열을 정리하여 가까운 순으로 반환하게 해보았다.

</aside>

코드 진행

(1) 최소힙 직접 구현

<aside> 👉🏿 최소힙을 직접 구현하는 부분은 따로 풀이를 하지 않겠다.

</aside>

class BinaryMinHeap:
    def __init__(self):
        self.items = [None]

    def __len__(self):
        return len(self.items) - 1

    def _percolate_up(self):
        cur = len(self)
        parent = cur // 2

        while parent > 0:
            if self.items[cur] < self.items[parent]:
                self.items[cur], self.items[parent] = self.items[parent], self.items[cur]

            cur = parent
            parent = cur // 2

    def _percolate_down(self, cur):
        smallest = cur
        left = 2 * cur
        right = 2 * cur + 1

        if left <= len(self) and self.items[left] < self.items[smallest]:
            smallest = left

        if right <= len(self) and self.items[right] < self.items[smallest]:
            smallest = right

        if smallest != cur:
            self.items[cur], self.items[smallest] = self.items[smallest], self.items[cur]
            self._percolate_down(smallest)

    def insert(self, k):
        self.items.append(k)
        self._percolate_up()

    def extract(self):
        if len(self) < 1:
            return None
        root = self.items[1]
        self.items[1] = self.items[-1]
        self.items.pop()
        self._percolate_down(1)

        return root

<aside> 👉🏿 최소힙은 만들었고 위 최소힙을 이용해서 문제를 풀어보자.

먼저 최소힙과 거리들을 계산한 리스트를 넣을 dists에 각각의 포인터들의 거리를 계산하여 넣는다.

</aside>

def kClosest(self, points, k):
        heap = BinaryMinHeap()              # 최소힙 생성
        dists = []                          # 각 포인터들의 거리 집합
        # 모든 point를 돌면서
        for point in points:
            # point와 원점의 거리를 계산한다.
            dist = calc(point[0], point[1])
            # heap과 dists에 넣기
            heap.insert(dist)
            dists.append(dist)

<aside> 👉🏿 추출을 진행한다.

최소 순으로 추출이되기 때문에 k번째까지 추출한 값을 지정한다.

</aside>

kth_dist = [heap.extract() for _ in range(k)][-1]