[Python] 658. Find K Closest Elements

정지은·2022년 9월 29일
0

코딩문제

목록 보기
2/25

658. Find K Closest Elements

문제

Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.

An integer a is closer to x than an integer b if:

|a - x| < |b - x|, or
|a - x| == |b - x| and a < b

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

접근

#이차원배열 #큐 #정렬
n-x의 값을 idx와 함께 이차원배열의 형태(queue)로 저장한 뒤, n-x의 값이 작은 순서대로 k개를 뽑아 리턴한다. 인덱스 순서는 정렬되어야 하므로 마지막에 sort한다.

처음에는 포인터 두 개를 사용해 while문으로 시도했으나, 여러 예외사항이 있어 알고리즘을 수정했다.

코드

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        arr1 = [[abs(n-x),i] for i,n in enumerate(arr)] # arr에서 n-x값을 따로 빼내 저장한다.
        arr1.sort(key = lambda x:x[0]) # 이차원배열을 n-x 순서대로 정렬한다.
               
            
        return sorted([arr[arr1[i][1]] for i in range(k)]) # k개만큼 꺼내어 정렬한다.
        

효율성

Runtime: 472 ms, faster than 61.64% of Python3 online submissions for Find K Closest Elements.
Memory Usage: 16.7 MB, less than 5.36% of Python3 online submissions for Find K Closest Elements.

profile
Steady!

0개의 댓글