[LeetCode] 658. Find K Closest Elements (Python)

658번문제 링크

https://leetcode.com/problems/find-k-closest-elements/

 

문제설명

입력: 정렬된 정수 배열 arr, 두 정수 k, x

출력: x와 가장 가까운 정수 k개를 담은 오름차순 배열

예시로 x와 더 가까운 것에 대한 정의로는

비교하고자 하는 값과 x의 차의 절댓값이 작은 것이 더 가까운 것으로 정의되고

절댓값이 같을경우 값이 더 작은 것이 x와 더 가까운 것으로 정의된다.

 

문제예제

Example1에서 보면 x = 3 이기 때문에

3과 가장 가까운 arr의 원소들을 살펴보면

(문제 정의에 따르면) 3, 2, 4, 1, 5 순서대로 arr과 가까운 것을 알 수 있다.

 

문제풀이

1. arr의 정렬순서를 x와 가장 가까운 순으로 정렬 하고자 했다. 

2. sorted 함수를 이용하여 |a-x|이 가장 작은 순으로 정렬한다.

3. 정렬된 배열을 k개 만큼 자른다.

4. 배열을 오름차순으로 정렬한다.

5. return 배열

 

정답코드

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        arr = sorted(arr, key = lambda a:abs(a-x))
        arr = arr[:k]
        arr.sort()
        return arr

풀이 후 생각정리

파이썬이 정말 간편한 것같다. sorted 함수에 key 설정을 통해 쉽게 풀이하였다.

C,C++,Java 였다면 다른 방법으로 풀었을 것 같다.

 

속도가 빠른 풀이들을 보면 Binary Search를 이용해 푸는 것 같았다.

BS가 훨씬 속도 향상에 도움이 되는건 인정.. 그치만 어렵고 머리 아픈 것 같다,,

어려움을 극복해야 실력이 늘텐데..

 

아래는 LeetCode에 upvote가 가장 많은 파이썬 풀이이다.

def findClosestElements(self, A, k, x):
        left, right = 0, len(A) - k
        while left < right:
            mid = (left + right) / 2
            if x - A[mid] > A[mid + k] - x:
                left = mid + 1
            else:
                right = mid
        return A[left:left + k]

풀이가 엄청 간단하다. 나는 왜 이런 생각을 못했을까.. 정말 똑똑하다...