15. 세 수의 합(3 Sum)

문제

정수 배열 nums가 주어졌을 때, 다음 조건을 만족하는 모든 세 수의 조합 [nums[i], nums[j], nums[k]]을 반환하라. * i != j, i != k, j != k (서로 다른 인덱스를 가져야 함) * nums[i] + nums[j] + nums[k] == 0 (세 수의 합이 0이 되어야 함) * 단, 중복된 조합은 포함하지 않아야 한다.

https://leetcode.com/problems/3sum/description/

 

예시

Example 1: Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Explanation:  nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1,-1,2]. Notice that the order of the output and the order of the triplets does not matter. Example 2: Input: nums = [0,1,1] Output: [] Explanation: The only possible triplet does not sum up to 0. Example 3: Input: nums = [0,0,0] Output: [[0,0,0]] Explanation: The only possible triplet sums up to 0.

 

제약

* 3 <= nums.length <= 3000 * -10^5 <= nums[i] < = 10^5

 

1) Brute Force 풀이

import java.util.*;
public class ThreeNumberSum01TimeOut {
    public static void main(String[] args) {

        int[] nums = {-1, 0, 1, 2, -1, -5};
        List<List<Integer>> result = threeNumberSum(nums);
        System.out.println(result);

    }

    // 1 - Brute Force => O(N^3)
    public static List<List<Integer>>threeNumberSum(int[] nums) {

        Arrays.sort(nums); // {-5, -1, -1, 0, 1, 2}; => O(NlogN)

        List<List<Integer>> result = new LinkedList<>();

        for (int i = 0; i < nums.length - 2; i++) {
            
            // 중복 값 예외처리
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            
            for (int j = i + 1 ; j < nums.length - 1; j++) {
                
                // 중복 값 예외처리
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }

                for (int k = j + 1; k < nums.length; k++) {
                    
                    // 중복 값 예외처리
                    if (k > j + 1 && nums[k] == nums[k - 1]) {
                        continue;
                    }

                    if (nums[i] + nums[j] + nums[k] == 0) {
                        result.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    }
                }
            }
        }

        return result;
    }
}

 

가장 단순한 방법으로 '완전탐색(Brute Force)'을 적용해볼 수 있다. 

단, 문제에 '중복된 조합은 포함되어야 하지 않아야 한다'는 조건이 있으므로  중복 값 예외처리 하는 로직이 필요하다.

// 중복 값 예외처리
if (i > 0 && nums[i] == nums[i - 1]) {
    continue;
}

 

배열이 정렬된 상태에서는 '연속된 값의 중복 여부'를 판단하여 데이터 중복 저장을 방지할 수 있다.

그림에서 볼 수 있듯이 이중 혹은 삼중 Loop를 순회할 때, 연속된 인덱스에 동일한 값이 나타나면 조합이 중복해서 발생하게 된다.

연속된 값을 비교하여 중복된 값이 등장했을 때, continue 키워드를 사용하여(= 다음번 인덱스의 원소로 skip) 간단히 중복 조합 저장을 방지할 수 있다.

 

하지만 삼중 Loop의 시간복잡도는 O(N^3)이고 문제 제약 조건에서 최대 배열의 길이가 3000이므로 해당 풀이는 timeout이 발생한다.

 

2) 투 포인터를 활용한 풀이

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class ThreeNumberSum02 {
    public static void main(String[] args) {

        int[] nums = {-1, 0, 1, 2, -1, -5};
        List<List<Integer>> result = threeNumberSum(nums);
        System.out.println(result);

    }

    // 1 - Two Pointer => O(N^2)
    public static List<List<Integer>>threeNumberSum(int[] nums) {

        int left, right, sum;
        Arrays.sort(nums); // {-5, -1, -1, 0, 1, 2}; => O(NlogN)
        List<List<Integer>> result = new LinkedList<>();

        for (int i = 0; i < nums.length - 2; i++) {
            // 중복 값 skip
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            // 이후부터 two pointer로 탐색
            left = i + 1;
            right = nums.length - 1;
            while (left < right) {
                sum = nums[i] + nums[left] + nums[right];
                if (sum < 0) {
                    left++;
                }
                else if (sum > 0) {
                    right--;
                }
                else { // sum == 0

                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    // *중복값 건너뛰기*
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }

                    // 정답이 나왔으므로 투 포인터 모두 한 칸씩 이동
                    // 합이 0인 상황이므로, 양쪽 모두 이동 필요!
                    left++;
                    right--;
                }
            }

        }

        return result;
    }
}

 

투 포인터를 활용한 풀이는 다음과 같다.

 

0. 배열을 오름차순으로 정렬

 

1. 연속적으로 중복된 원소를 제외하고(-> 중복된 조합 저장 방지), 각 원소를 순회하며 다음에 나오는 값들에 대해서 '투 포인터'를 적용

• i : 기준이 되는 원소
• left : 투 포인터 중 왼쪽 포인터
• right : 투 포인터 중 오른쪽 포인터

2. 세 값의 합(nums[i] + nums[left] + nums[right])을 '0'과 비교하여 투 포인터 조정

• sum < 0 이면, left 한칸 이동 (=> sum 값을 키움)
• sum > 0 이면, right 한칸 이동 (=> sum 값을 줄임)
• sum == 0 이면, 
  • 1) result 리스트에 값 저장
  • 2) 투 포인터 중 left 부분에서 연속된 중복 값이 있는지 체크 -> 중복 조합 저장 방지
  • 3) 투 포인터 중 right 부분에서 연속된 중복 값이 있는지 체크 -> 중복 조합 저장 방지
  • 4) 정답이 나왔으므로 양쪽 투 포인터 모두 한칸 이동
    • WHY) 왜 두 포인터 모두 한 칸씩 이동해야 하는가? 한 쪽만 이동해서 확인해야 하는 경우도 있지 않을까?
    • ANSWER) 두 값이 고정된 상태에서 하나만 이동했을 때 또 다시 정답이 나오는 경우는 '중복된 데이터'인 경우 밖에 없음. 하지만 그러한 경우는 문제 조건에 의해 정답이 될 수가 없다.

 

 

이렇게 투 포인터를 활용하면 

 

• 오름차순 정렬 -> O(NlogN)
• 배열의 각 원소를 FOR LOOP로 순회 -> O(N)
  • 투 포인터가 While 문 안에서 left부터 right 까지 순회 -> O(N)

 

최종적으로 O(N^2) 시간 안에 동작할 수 있게 된다.