[LeetCode] 16. 3Sum Closeset

문제 출처: https://leetcode.com/problems/3sum-closest/

3Sum Closest - LeetCode

 

문제

n개의 정수로 이루어진 배열 nums와 정수 target이 주어지면, target과 가장 근접한 배열 내의 세 정수의 합을 찾아서 반환하라. 각 입력에는 정확히 하나의 정답이 있다고 가정할 수 있다.

 

예제

Input: nums = [-1,2,1,-4], target = 1
Output: 2

Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

 

풀이

3중 루프 _ O(n³)

가장 손쉽게 떠올릴 수 있는 방법은 3중 루프를 이용한 방법일 것이다. 모든 가능한 경우의 수를 체크하면서 target과 가장 근접한 값을 찾으면 된다.

var threeSumClosest = function(nums, target) {
    let ans = Infinity;
    
    for (let i = 0; i < nums.length-2; i++) {
    	for (let j = i+1; j < nums.length-1; j++) {
            for (let k = j+1; k < nums.length; j++) {
                const tmpSum = nums[i] + nums[j] + nums[k];
                if (Math.abs(ans - target) > Math.abs(tmpSum - target)) {
                    ans = tmpSum;
                }
            }
        }
    }
    
    return ans;
}

위 코드와 같이 작성할 수 있고, 다행스럽게도 O(n3) 임에도 테스트 케이스를 제 시간 안에 모두 통과한다.

 

다만, O(n³)이라는 비효율적인 시간 복잡도를 보이는 만큼 개선 방안에 대해 생각해볼 필요가 있다.

 

이진 탐색 _ O(n²logn)

처음으로 생각할 수 있는 개선 방법은 이진 탐색 기법을 사용하는 것이다.

 

위 코드에서 k에 대한 반복을 이진 탐색으로 대체하는 것이다. k를 탐색하는 시점에 대해 생각해보면, 이미 2개의 정수(nums[i], nums[j])를 선택한 상황이기 때문에 target에 근접하게 하는 단일한 1개의 값을 찾는 문제로 생각할 수 있고 이를 이진탐색으로 찾자는 것이다.

 

이진탐색을 수행할 때, 한 가지 생각할 점은 kTarget = target - nums[i] - nums[j] 라고 할 때 nums 내에 kTarget이 존재하지 않을 수 있다는 것이다. 그래서 실제로 찾아야 하는 값은 kTarget보다 처음으로 큰 값이 나오는 지점을 찾고, 찾아진 지점과 찾아진 지점보다 -1 인 지점에서 kTarget과 비교를 통해 더 작은 차를 갖는 지점을 선택해야 한다.

var threeSumClosest = function(nums, target) {
    let diff = Infinity;
    
    // 이진 탐색을 위한 정렬
    nums.sort((prev, next) => prev-next);
    
    for (let i = 0; i < nums.length-2; i++) {
    	for (let j = i+1; j < nums.length-1; j++) {
            const val = target - nums[i] - nums[j];
            const hi = bisectUpper(nums, val, j+1);
            const lo = hi - 1;
            if (hi < nums.length && Math.abs(val - nums[hi]) < Math.abs(diff)) {
            	diff = val - nums[hi]
            }
            if (lo > j && Math.abs(val - nums[lo]) < Math.abs(diff)) {
            	diff = val - nums[lo]
            }
        }
    }
    return target - diff;
}

var bisectUpper = function(nums, target, lo) {
    let hi = nums.length;
    while (lo < hi) {
    	const mid = lo + Math.floor((hi-lo) / 2);
        if (target >= nums[mid]) {
        	lo = mid + 1;
        } else {
        	hi = mid;
        }
    }
    return lo;
}

이 코드의 시간 복잡도를 생각해보면, 정렬하는데 O(nlogn)이 소요될 것이고, 3개의 정수를 택하는 반복문에서 O(n²logn)이 소요될 것이기 때문에 전체적으로 O(n²logn)의 시간복잡도를 갖는다고 말할 수 있다.

 

투 포인터 _ O(n²)

마지막으로 언급할 방법은 Two-Pointer 기법을 이용한 방법이다.

 

이진 탐색을 이용한 방법에서는 두 개의 정수를 미리 선택해놓고 나머지 한 개의 정수를 찾았다면, 투 포인터에서는 한 개의 정수를 선택해놓고 나머지 두 개의 정수를 찾는 방식으로 해답을 찾는 것이다.

 

우선 이 방법 역시도 정렬된 배열에서 수행된다.

 

위에서 언급한 것처럼 하나의 값을 미리 정하고 나머지 두 개의 값을 찾는데, i 위치의 정수를 미리 선택했다고 하자. 이 상황에서 나머지 두 정수를 찾는 문제를 풀어보자.

 

탐색해야 하는 범위는 i+1위치부터 배열의 끝 위치이다. 이 범위에서 lo와 hi 라는 두 포인터를 사용할 것이고 두 포인터의 초기 위치는 각각 lo = i+1, hi = n-1 이 된다. 정렬이 되어있기 때문에 lo가 가리키는 위치에는 탐색 범위 중 가장 작은 값이 들어가 있을 것이고, hi 위치에는 범위 중 가장 큰 값이 들어가 있음을 기억하자.

 

sum = nums[i] + nums[lo] + nums[hi] 이라 하면, target과 비교하여 다음과 같이 두 가지 움직임을 가져갈 수 있다.

• sum > target: hi = hi - 1
• sum < target: lo = lo + 1

이 과정을 통해서 i 위치의 값을 고정적으로 가져갈 때, target과 가장 가까운 3 정수의 합을 구할 수 있다. 코드로 작성해보면 아래와 같다.

var threeSumClosest = function(nums, target) {
    let diff = Infinity;
    nums = nums.sort((prev, next) => prev - next);
    
    for (let i = 0; i < nums.length && diff != 0; i++) {
        let lo = i+1, hi = nums.length-1;
        while (lo < hi) {
            const sum = nums[i] + nums[lo] + nums[hi];
            
            if (Math.abs(target - sum) < Math.abs(diff)) {
                diff = target - sum;
            }
            
            if (sum < target) {
                lo += 1;
            } else {
                hi -= 1;
            }
        }
    }
    
    return target - diff;
};

 

Github: 16.js

GitHub - opwe37/Algorithm-Study