[LeetCode] 15. 3Sum

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

3Sum - LeetCode

---

문제

정수 배열 nums가 주어집니다. nums[i] + nums[j] + nums[k] == 0 이고, i != j, i !=k, 그리고 j != k 인 모든 [nums[i]m nums[j], nums[k]를 찾아라.

 

중복된 케이스는 답에 포함되어서는 안 된다.

예제

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

---

풀이

전형적인 세 수의 합을 계산하는 알고리즘을 작성하는 문제입니다.

 

세 수의 합을 알기 위해서는 반드시 세 수를 찾아야만 합니다. 만약, 세 수가 $x$, $y$, 그리고 $z$라고 한다면

$x + y + z = 0$인 케이스를 찾고자 하는 것이고, 이는 $x = -(y + z)$ 인 것을 찾는 것과 같습니다. 여기서 x를 고정된 값으로 생각한다면 두 수의 합을 찾는 문제가 됩니다.

var threeSum = funtion(nums) {
    const answer = [];
    if (nums.length < 3) { return answer; }
    
    for (let x = 0; x < nums.length-2; x++) {
    	// [TODO] 두 수의 합 계산(y + z = -x 인 케이스 찾기)
    }
    
    return answer;
}

두 수를 효과적으로 찾기 위해서 투-포인터 기법을 사용할 수 있습니다.

 

투-포인터 기법을 통해 합이 특정 값이 되는 두 수를 찾는 방식에 대해 간략히 설명하면 다음과 같습니다.

 

1. 정렬된 배열(arr)을 가정합니다.
2. 탐색할 범위의 가장 낮은 지점에 left 포인터를, 가장 높은 지점에 right 포인터를 위치시킵니다.
3. arr[left] + arr[right]와 target을 비교하여 각 케이스에 대해 다음의 행동을 취합니다.
   • arr[left] + arr[right] > target : right 위치를 1 감소시킨다. (right를 그대로 두게 되면 left가 변화해도 arr[left] + arr[right] > target 유지됨)
   • arr[left] + arr[right] < target : left 위치를 1 증가시킨다. (left를 그대로 두게 되면 right가 변화해도 arr[left] + arr[right] < target 유지됨)
4. arr[left] + arr[right] == target의 케이스를 찾거나 left < right 조건이 유지되는 한 3의 과정을 반복합니다.

위 코드에서 비워두었던 곳을 채워보도록 하겠습니다. (left == y, right == z)

var threeSum = funtion(nums) {
    const answer = [];
    if (nums.length < 3) { return answer; }
    
    // 투 포인터 기법을 사용하기 위해 정렬
    nums.sort((a, b) => a - b);
    
    for (let x = 0; x < nums.length-2; x++) {
    	let y = x + 1;
        let z = nums.length - 1;
        while (y < z) {
            const sumVal = nums[x] + nums[y] + nums[z];
            
            if (sumVal > 0) {
            	z -= 1;
            } else if (sumVal < 0) {
            	y += 1;
            } else {
            	answer.push([nums[x], nums[y], nums[z]]);
                break;
            }
        }
    }
    
    return answer;
}

자, 위 코드의 문제점을 찾아볼까요?

 

1. 고정된 x에 대해 한 가지의 케이스 밖에 찾지 못함
   • 예를 들어, x == 3이라 하면, -3을 만드는 케이스는 y == -2, z == -1 혹은 y == -4, z == 1과 같이 여러 케이스가 존재할 수 있는데 위 코드는 이러한 케이스를 모두 찾지 않음
2. 중복 케이스에 대한 고려가 없음
   • 만약 nums 배열에 -2가 두 번 등장한다고 가정하면, x로 -2가 두 번 선정될 테고 이때 동일한 케이스가 결과에 추가됨

각 문제를 하나씩 해결해보도록 하겠습니다.

 

첫 번째 문제는 투-포인터 기법 안에서 break 구문 때문입니다. break 구문 대신에 다음 y 혹은 z로 이동하여 다음 케이스를 찾을 수 있도록 해야 합니다. 저는 y 값을 1 증가시키는 것으로 다음 값을 찾을 수 있도록 하였습니다.

var threeSum = funtion(nums) {
    const answer = [];
    if (nums.length < 3) { return answer; }
    
    nums.sort((a, b) => a - b);
    
    for (let x = 0; x < nums.length-2; x++) {
    	let y = x + 1;
        let z = nums.length - 1;
        while (y < z) {
            const sumVal = nums[x] + nums[y] + nums[z];
            
            if (sumVal > 0) {
            	z -= 1;
            } else if (sumVal < 0) {
            	y += 1;
            } else {
            	answer.push([nums[x], nums[y], nums[z]]);
                
                // y 값 1 증가
                y += 1;
            }
        }
    }
    
    return answer;
}

두 번째 문제는 x와 y(혹은 z)에 이전과 동일한 값이 사용되지 않도록 하는 것으로 문제를 해결할 수 있습니다. 

var threeSum = funtion(nums) {
    const answer = [];
    if (nums.length < 3) { return answer; }
    
    nums.sort((a, b) => a - b);
    
    for (let x = 0; x < nums.length-2; x++) {
    	// x가 동일한 값으로 설정되는 것 방지
    	if (x !== 0 && nums[x] === nums[x-1]) { continue; }
        
    	let y = x + 1;
        let z = nums.length - 1;
        while (y < z) {
            const sumVal = nums[x] + nums[y] + nums[z];
            
            if (sumVal > 0) {
            	z -= 1;
            } else if (sumVal < 0) {
            	y += 1;
            } else {
            	answer.push([nums[x], nums[y], nums[z]]);
                
                // y가 동일한 값으로 설정되는 것 방지
                const prevY = nums[y]
                while (y < z && nums[y] == prevY) { y += 1; }
            }
        }
    }
    
    return answer;
}

모든 문제가 해결되었습니다.

 

이제 코드의 시간 복잡도에 대해 생각해보겠습니다. 기본적으로 정렬과 투-포인터 기법은 다음과 같은 시간 복잡도를 갖습니다.

• 배열 정렬: $O(nlogn)$
• 투-포인터: $O(n)$

 

여기서 투-포인터 알고리즘은 $n-2$번 실행되기 때문에 $O(n^2)$의 시간 복잡도를 생성하게 됩니다. 최종적으로 $nlogn + n^2$만큼의 시간이 걸리지만 빅오 표기법에 의해 $O(n^2)$의 시간 복잡도를 갖는다고 말할 수 있습니다.

 

Github: 15.js

GitHub - opwe37/Algorithm-Study