[Leetcode] 15번 - 세 수의 합

1. 문제 파악

• 문제 링크: https://leetcode.com/problems/3sum/
• 문제 요구사항: 주어진 배열에서 3개의 요소의 합이 0인 리스트중에서 중복되지 않는 리스트들을 반환해라.
• 시간복잡도: 입력 크기가 3000개이므로 O(N^2)내의 풀이를 작성해야한다.

---

2. 문제 풀이

1. 브루트 포스로 문제 풀이 도출

주어진 배열의 요소를 3개 골라야되므로 시간복잡도는 O(N^3)이다.

for (int i = 0; i < n; i++) 
  for (int j = i + 1; j < n; j++)
    for (int k = j + 1; k < n; k++)
      if (nums[i] + nums[j] + nums[k] == 0) ...

2. 핵심 문제 풀이 도출: 어떻게 하면 시간복잡도 내로 풀수있을까?

브루트포스로 풀면 O(N^3)이 나온다. 따라서 O(N^2) 이내로 풀어야한다.

 

세 개를 고르는데 O(N³)이니까 줄일 수 있는 방법은 없을까?

 

배열에서 요소를 하나 지정해놓고 배열을 한번 순회해서 처리할수있다면 O(N^2)이 걸릴것이다. 그렇다면 지정된 요소외에 배열을 한번 순회할때동안 다른 두개를 가리키는 포인터를 움직이면서 처리하면 O(N^2)이 걸린다.

 

즉, 기준점만 지정해놓으면 투포인터를 사용해서 O(N^2) 걸릴것을 O(N)으로 줄일수있다. 그리고 기준점을 바꾸는 것은 배열 순회가 한번 필요하므로 O(N)이 걸려서 총 O(N) X O(N) = O(N^2)이 걸린다.

 

그러나 주어진 배열에서 투포인터를 움직일수 있는 조건이 필요하다. 움직이는 조건은 원하는 답이 아니여서 답을 좁혀나가기 위해 움직이는 것이다.

 

숫자들의 합이 0을 만족하는 수들을 구해야하므로 숫자의 합이 0보다 크다/작다로 두개의 포인터가 움직이는 것을 생각해볼수있다. 따라서 배열을 먼저 정렬된 상태여야 두 포인터의 합을 크거나 작도록 움직일수있다. 이로써 기준점을 기준으로 두개의 포인터가 조건에 따라 이동할수있다. 정렬은 O(nlogn)이므로 O(n^2)을 넘지 않는다.

 

3. 입출력 케이스 도출 및 문제 풀이 도출 확인

• 일반케이스
  • Example1
    • Input: nums = [-1,0,1,2,-1,-4]
    • Output: [[-1,-1,2],[-1,0,1]]
  • Example2
    • Input: nums = [0, 0, 0]
    • Output: [[0, 0, 0]]
• 엣지 케이스
  • Example1
    • Input: nums = [-1,0,1,1,2,2,-1,-4]
    • `Output: [[-1,-1,2],[-1,0,1],[-4,2,2]]

Output에서 중복값을 반환하면 안된다. 따라서 중복을 제거하는 로직이 필요하다. 아래에서 위의 핵심 문제 풀이 로직이 동작하는데 중복되는 지점을 찾아서, 중복 로직을 생각하고 구현할것이다.

 

4. 코드로 문제 풀이 구현

만일, 입력 케이스가 [-1,0,1,1,2,2,-1,-4]이면, 오름 차순 정렬시 [-4,-1,-1,0,1,1,2,2]이다. 아래와 같이 i를 기준으로 i보다 하나 큰 j와 맨 마지막 k를 시작점으로 안쪽으로 j와 k 포인터를 좁혀나가면 완전 탐색을 할수있다.

# i를 기준점으로 j와 k가 양쪽에서 좁하나가며 움직임
 i  j->        <-k
-4 -1 -1 0 1 1 2 2

    i  j->     <-k
-4 -1 -1 0 1 1 2 2

       i j->   <-k
-4 -1 -1 0 1 1 2 2

...

             i j k
-4 -1 -1 0 1 1 2 2

 

그리고 nums[i] + nums[j] + nums[k] == 0을 찾으면, 리스트를 생성해서 배열 요소를 추가하면된다.

 i  j->        <-k
-4 -1 -1 0 1 1 2 2

 i             j k
-4 -1 -1 0 1 1 2 2

 

i를 기준으로 합이 0인 요소를 모두 찾아야하므로 j < k일때동안, 부합하는 모든 리스트를 생성해서 배열 요소를 추가해야한다. 그리고 반환해야될 리스트(List<List<Integer>>)에 리스트(List<Integer>)를 추가한다.

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> resultList = new ArrayList<>();
    Arrays.sort(nums); // 투포인터를 위해 정렬
    int n = nums.length;
    for (int i = 0; i < n - 2; i++) { 
        int j = i + 1;
        int k = n - 1;

        while (j < k) {
            int sum = nums[i] + nums[j] + nums[k];
            if (sum < 0) {
                j++;
            } else if (sum > 0) {
                k--;
            } else {
                resultList.add(Arrays.asList(nums[i], nums[j], nums[k]));
                j++;
                k--;
            }
        }
    }
    return resultList;
}

 

그러나 출력값은 중복된 값으로 구성된 조합의 리스트는 추가하면 안된다. 아래와 같이 배열의 중복은 기준점인 i에서 중복값 발생할때와 투포인터(j, k)에서 중복 값 발생할때이다.

# 기준점인 i에서 중복값 발생할때
    i    j k
-4 -1 -1 0 1 1 2 2

       i j k
-4 -1 -1 0 1 1 2 2

# 투 포인터(j, k)에서 중복 값 발생할때
    i    j k
-4 -1 -1 0 1 1 2 2

    i    j   k
-4 -1 -1 0 1 1 2 2

 

그러므로 3개의 조합으로 이루어진 리스트 추가를 수행하고, 이전에 추가했던 조합은 건너뛰는 로직을 생각해야한다.

i뒤에는 바로 j와 k가 오기 때문에 i가 이전 i와 중복될 경우에는 스킵해야한다. 따라서 i가 이전 값 i-1와 중복될 경우에는 스킵한다.

j와 k도 각각 이전 값이 중복될때 한칸씩 각 포인터 방향으로 이동시켜야하므로, j와 k가 j-1과 k+1의 요소값이 중복될경우 스킵한다.

// 기준점 i 중복 제거
if (i > 0 && nums[i] == nums[i - 1]) continue;

// 왼쪽 포인터 j 중복 제거
while (j < k && nums[j] == nums[j + 1]) j++;

// 오른쪽 포인터 k 중복 제거
while (j < k && nums[k] == nums[k - 1]) k--;

 

따라서 최종 코드는 다음과 같다.

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> resultList = new ArrayList<>();
        Arrays.sort(nums); // 투포인터를 위해 정렬
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) { 
            // 이전에 추가했던 조합은 건너뛰기 (i 다음에 바로 j와 k가 오기때문에 i-1는 이미 포함됨)
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 기준점 중복 제거
            int j = i + 1; // 왼쪽 포인터
            int k = n - 1; // 오른쪽 포인터
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];

                if (sum < 0) {
                    j++; // 합이 0보다 작은 경우 큰 요소값으로 이동
                } else if (sum > 0) {
                    k--; // 합이 0보다 작은 경우 작은 요소값으로 이동
                } else {
                    // 합 0이면, 리스트에 추가
                    resultList.add(Arrays.asList(nums[i], nums[j], nums[k]));

                    // 이전에 추가했던 조합은 건너뛰기
                    while (j < k && nums[j] == nums[j + 1]) j++; // 왼쪽 요소값 중복 제거 
                    while (j < k && nums[k] == nums[k - 1]) k--; // 오른쪽 요소값 중복 제거

                    j++;
                    k--;
                }
            }
        }
        return resultList;
    }
}

 

5. 복잡도

• 시간 복잡도
  • 기준점 순회: O(N)
  • 투포인터 순회: O(N)
  • 최종 시간복잡도: 기준점 순회 x 투포인터 순회 = O(N^2)
• 공간 복잡도
  • 추가 공간은 반환값의 개수(K)을 저장한 결과 리스트에 한정되므로 O(K)이다.