Heap-PrioiryQueue: 973. K Closest Points to Origin ★

973. K Closest Points to Origin

 

https://youtu.be/rI2EBUEMfTk?si=rQzq5oqyjL2M1qgb

 

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        # k번째 가까운 points 리턴,
        # [distance, x, y] 로 저장
        # minHeap 사용
        minHeap = []

        for x, y in points:
            dist = (x**2) + (y**2)
            minHeap.append([dist, x, y])

        heapq.heapify(minHeap)

        res = []
        while k > 0:        
            dist, x, y = heapq.heappop(minHeap)
            res.append([x, y])
            k -=1

        return res

 

최종 코드

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        # k 번째 가까운거까지 찾는 것이니, 최소 힙으로
        distance_points = []
        for p in points:
            d = sqrt(p[0]*p[0]+p[1]*p[1])
            distance_points.append([d, p[0], p[1]])

        heapq.heapify(distance_points)

        res = []
        for i in range(k):
            # res.append([distance_points[0][1], distance_points[0][2]])
            # heapq.heappop(distance_points)
            d, x, y = heapq.heappop(distance_points)
            res.append([x, y])
        return res