64. K Closest Points to Origin

- 파이썬 알고리즘 인터뷰 64번 문제

2020.02.28

2 try

class Solution:
    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
        plist = []
        for x, y in points:
            plist.append([x, y, (x * x + y * y)])

        plist = sorted(plist, key=lambda x: x[2], reverse = True)
        result = []
        for _ in range(K):
            result.append(plist.pop()[:-1])
        return result

- plist에 [x좌표, y좌표, 거리^2]를 저장했다.
- plist를 거리값을 기준으로 '내림차순'으로 정렬했다. (큰 값이 앞으로 오게)
- 그리고 K개 만큼 plist.pop[:-1] 한 것을 result 리스트에 담았다.
(거리는 sorted의 key값으로 사용하기 위해 넣은 것이다. 결과를 출력할 때는 필요가 없다.)
- 최종적으로 result 리턴한다.

-

-

import heapq

class Solution:
    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
        heap = []
        for x, y in points:
            heapq.heappush(heap, (x * x + y * y, x, y))

        result = []
        for _ in range(K):
            result.append(heapq.heappop(heap)[1:])
        return result

- K번 추출이라는 단어에서 '우선 순위 큐'를 자연스럽게 떠올릴 수 있다.
- 값을 기준으로 최소힙을 만드는 heapq를 생성한다.
- heapq.headppop을 통해 K개 만큼 값을 뽑아 result 리스트에 넣는다.
- 단, heap의 첫번째 요소(거리값)는 필요 없으므로 heapq.heappop(heap)[1:] 슬라이싱한다.
- 최종적으로 result를 리턴한다. 

-