[LeetCode] Find K Closest Elements - 자바스크립트 풀이

문제 링크 

물론 얻어걸린 해답이다.

 

1. 접근 방법

 

(1) 주어지는 배열이 오름차순 정렬돼 있고, 특정 조건에 따라 피벗 값을 기준으로 검사 위치를 변경해가며 푸는 문제이므로 이진 탐색 문제다.

 

(2) left는 나중에 slice할 범위의 왼쪽 끝 인덱스다.

(3) right가 arr.length - k로 초기화되어 있는 이유는 left 인덱스로부터 k만큼 자르기 위해 가능한 최대 인덱스이기 때문이다.

    let left = 0;
    let right = arr.length - k;

 

(4) left <= right 로 while문을 도는 이유는 mid 값을 특정해서 알아내어 slice할 때 인덱스로 사용하고 싶어서다.

    while (left <= right) {
        let mid = left + Math.floor((right - left) / 2);
        // ...
    }

 

(5) 지금 mid 인덱스의 값과 x 까지의 차이와, mid + k 인덱스의 값과 x 까지의 차이를 비교한다.

비교해서 더 작은 쪽으로 left, right를 옮긴다.

    while (left <= right) {
        let mid = left + Math.floor((right - left) / 2);
        if (x - arr[mid] > arr[mid + k] - x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

 

(6) left부터 left + k까지 길이 k의 배열을 잘라 리턴한다.

    return arr.slice(left, left + k);

 

2. 전체 해답

/**
 * @param {number[]} arr
 * @param {number} k
 * @param {number} x
 * @return {number[]}
 */
var findClosestElements = function(arr, k, x) {
    let left = 0;
    let right = arr.length - k;
    
    while (left <= right) {
        let mid = left + Math.floor((right - left) / 2);
        if (x - arr[mid] > arr[mid + k] - x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return arr.slice(left, left + k);
};

의문만 남은 답안.,, 그냥 외우자^^!