자바스크립트 코딩테스트 강좌, 시간 복잡도 활용하기

문제 설명

주어진 배열 arr에서 특정 num 값과 가장 가까운 수를 찾는 문제입니다.
가장 가까운 수가 여러 개 있을 경우, num에 가까운 값이 더 낮을 경우를 우선합니다.

입력

정수 배열 arr (-10⁶ ≤ arr[i] ≤ 10⁶, 1 ≤ arr.length ≤ 10⁵)
정수 num (-10⁶ ≤ num ≤ 10⁶)

출력

가장 가까운 수를 반환합니다.

예제

예제 1:
입력: arr = [1, 2, 3, 4, 5], num = 3
출력: 3

예제 2:
입력: arr = [1, 2, 4, 5], num = 3
출력: 2

예제 3:
입력: arr = [5, 10, 15], num = 12
출력: 10

풀이 과정

이 문제를 해결하기 위해서 다음과 같은 단계를 따릅니다.

1단계: 문제 이해하기

우선 num과 가장 가까운 수를 찾는 문제이므로, 각 요소와 num의 차이인 절댓값을 계산하여 가장 작은 값을 찾는 것이 핵심입니다. 이때, 같은 차이 값을 가진 여러 개의 수가 있을 경우 더 작은 값을 반환해야 합니다.

2단계: 접근 방법 선정하기

가장 간단한 방법은 배열을 순회하며 각 요소의 절댓값 차이를 계산하는 것입니다. 하지만 이 방식은 O(n) 시간복잡도를 가지므로, 이보다 빠른 알고리즘을 고려해야 합니다.

3단계: 정렬을 통한 이진 탐색 활용하기

입력 배열을 정렬하면 이진 탐색을 통해 num 값에 가장 가까운 수를 효율적으로 찾을 수 있습니다. 정렬된 배열에서 특정 값 num 의 인덱스를 찾기 위해 Array.prototype.sort()를 사용하고, 이에 이어서 binarySearch() 함수를 구현합니다.

4단계: 코드 구현하기

다음은 위에서 설명한 내용을 바탕으로 작성한 자바스크립트 코드입니다.


function findClosest(arr, num) {
    // 배열 정렬
    arr.sort((a, b) => a - b);
    
    let left = 0;
    let right = arr.length - 1;
    let closest = arr[0];

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        // 절댓값 차이 비교
        if (Math.abs(arr[mid] - num) < Math.abs(closest - num) ||
            (Math.abs(arr[mid] - num) === Math.abs(closest - num) && arr[mid] < closest)) {
            closest = arr[mid];
        }
        
        // 이진 탐색의 방향 결정
        if (arr[mid] < num) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return closest;
}

// 예제 테스트
console.log(findClosest([1, 2, 3, 4, 5], 3)); // 3
console.log(findClosest([1, 2, 4, 5], 3));    // 2
console.log(findClosest([5, 10, 15], 12));      // 10

5단계: 시간 복잡도 분석

위 코드는 먼저 배열을 정렬합니다. 정렬의 시간 복잡도는 O(n log n)이며, 이후 이진 탐색을 이용한 탐색 과정에서는 O(log n)의 시간이 소요됩니다. 전체 시간 복잡도는 O(n log n)로 평가할 수 있습니다.

결론

이 문제를 통해 시간 복잡도를 고려하여 효율적인 알고리즘을 선택하는 것이 얼마나 중요한지를 배웠습니다. 주어진 문제에 대해 다양한 접근 방식을 시도하고, 그 결과에 따라 적절한 알고리즘을 선택하는 연습이 필요합니다. 앞으로의 코딩테스트에서도 이러한 원칙을 잘 활용하시길 바랍니다!