[LeetCode] 973. K Closest Points to Origin (파이썬)

542. K Closest Points to Origin - 파이썬 풀이

< 목차 >

1. 문제접근 아이디어
2. 구현코드

문제접근 아이디어

• 해당 문제는 입력되는 point의 개수가 최대 10,000개이다. 그래서 그냥 반복문을 이용해서 해결할 수 있을 것이라 생각된다.
• 요구하는 것은 유클리드 거리가 짧은 순서대로 k만큼 반환하라는 것이다.
• 계산된 특정 값을 이용하여 정렬을 하는 것을 생각할 때 가장 편리하게 사용할 수 있는 것은 내 생각으론 우선순위 큐이다.
• 유클리드 값을 계산 해서 파이썬 라이브러리 heapq에 넣으면 정렬이 되어있다.
• 이 값을 음수로 바꿔서 넣으면 거리가 제일 긴 것이 pop을 하면 나올 것이다.
• 그리고 우선순위 큐에 요소의 수를 len()으로 세어서 내가 원하는 값보다 더 크면 pop을 해서 빼내면 끝이다.
• 만약에 여기서 x나 y 좌표가 작은 순서로 반환하라 했으면 추가적인 정렬을 했어야한다.

구현코드

import heapq
class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        minList = []
        for x, y in points:
            cmp = -(pow(x,2)+pow(y,2))
            heapq.heappush(minList, (cmp, x, y))
            if len(minList) > k:
                heapq.heappop(minList)
        return [minList[i][1:] for i in range(len(minList))]