Leetcode 973. K Closest Points to Origin (Heaqp 등)

https://leetcode.com/problems/k-closest-points-to-origin/

K Closest Points to Origin - LeetCode

 

---

 

처음 접근)

from collections import OrderedDict

class Solution:
     def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
         q= [] ; ck = {}
        
         for i in points:
             d1, d2 = i
             dist = d1**2 + d2**2
             if dist not in ck.keys():
                 ck[dist] = i
        
         ck = OrderedDict(sorted(ck.items()))
        
         return list(ck.values())[:k]

처음에는 points의 거리 계산 값을 dict 형태로 저장한 뒤, key값을 기준으로 딕셔너리를 정리해서 반환하는 방법을 선택했다. 하지만, key의 중복을 허용하지 않는 dict의 특성상 [0,1] [1,0] 처럼 거리가 1로 동일한 경우를 구분하지 못하는 에러가 발생했다.

 

 

---

재밌는 풀이가 여러개 있었는데 그 중에 대표적인 몇가지를 분석해보려 한다.

코딩은 생각하는 방법을 기르는 것이라고 들었는데 여러 풀이를 보면 하나의 문제에 참 다양한 풀이가 가능하구나 싶어서 흥미롭고, 다른 사람의 생각을 엿보는 것 같아서 즐겁다 ㅎㅎㅎㅎ

 

다른 풀이 1 ) sorted 조건 지정을 통한 simple 한 방식

 

class Solution:
	def kClosest(self, P,k):
    	return sorted(P, key = lambda p : p[0]**2 + p[1]**2)[:k]

보면 간단한 방식을 왜 생각 못했지 싶고 직관적인 코드가 인상적이다

 

 

다른 풀이 2 ) Heap과 enumerate을 사용한 MAX HEAP 반환 방법

class Solution:
	def kClosest(self,p,k):
    	heap, dist = [], lambda x,y : x**2 + y**2
        
        for i, (x,y) in enumerate(P):
        	d = dist(x,y)
            
            if len(heap) == k:
            	heappushpop(heap,(-d,i))
            else:
            	heappush(heap,(-d,i))
                
         return [P[i] for (_,i) in heap]

enumerate을 통해서 인덱스 값을 keep 해두고  max로 정렬된 heap에서 i 값을 통해서 정답을 도출 했다

 

 

다른 풀이 3 ) 또 다른 MAX HEAP 반환 방법

 

heap = []

for (x,y) in points:
	dist = -(x**2 + y**2)
    
    if len(heap) == K:
    	heapq.heappushpop(heap,(dist,x,y))
    else:
    	heapq.heappush(heap,(dist,x,y))
        
return [(x,y) for (dist,x,y) in heap]

 

2번째 풀이와 접근법은 동일하지만, 결과값을 도출하는 방식을 이번 방식은 heap에 (dist,x,y)를 넣어서 직접적으로 x,y값을 가져오도록 했다

 

 

**Heapq 개념은 하단의 게시물 참조

https://psygo22.tistory.com/46

Heapq 알고리즘 개념 및 활용방법 정리