[정렬] Leet code 973. K Closest Points to Origin

리트코드 973번
원점으로부터 k번째까지 가까운 점들 출력

풀이1 정렬함수

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        points = sorted(points, key= lambda x : x[0]**2 + x[1]**2)

        return points[:k]

• 1초가 좀 넘는다..

풀이2 우선순위 큐

import heapq

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        pq = []
        result = []
        for i,point in enumerate(points):
            heapq.heappush(pq, (point[0]**2 + point[1]**2, i))

        for i in range(k):
            result.append(points[heapq.heappop(pq)[1]])

        return result

• (거리^2 , index) 튜플을 값으로 넣어준다

• k번 pop하면서 index값에 해당되는 점들을 리스트에 넣어준다

• 정렬함수를 쓴것과 시간복잡도에서 별 차이가 없다..