[LeetCode] 3Sum - 하나를 고정하고 두 수를 찾기

이번에 정리할 문제는 LeetCode 15번 3Sum이다. 정수 배열 nums가 주어졌을 때, 서로 다른 세 인덱스 i, j, k를 골라 nums[i] + nums[j] + nums[k] = 0이 되는 모든 트리플렛을 찾아야 한다.

이 문제에서 중요한 조건은 두 가지다. 세 인덱스가 서로 달라야 하고, 결과에 중복된 트리플렛이 포함되면 안 된다.

문제

정수 배열 nums가 주어질 때, 다음 조건을 만족하는 모든 트리플렛을 반환해야 한다.

1. i, j, k는 서로 다른 인덱스여야 한다.
2. nums[i] + nums[j] + nums[k] = 0이어야 한다.
3. 중복된 트리플렛은 결과에 포함하면 안 된다.

제약 사항은 다음과 같다.

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

접근

브루트 포스로 생각해보기

가장 단순한 방법은 세 개의 인덱스를 모두 직접 고르는 것이다.

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        for (int k = j + 1; k < n; k++) {
            // nums[i] + nums[j] + nums[k] == 0 확인
        }
    }
}

이 방식은 모든 세 수의 조합을 확인하므로 시간 복잡도가 O(n^3)이다. 하지만 nums.length는 최대 3,000까지 가능하므로, 이 방법으로는 효율적으로 해결하기 어렵다.

따라서 세 수를 한 번에 모두 고르기보다는, 하나의 수를 먼저 고정하고 나머지 두 수를 찾는 방식으로 문제를 바꿔볼 수 있다.

하나를 고정하고 두 수를 찾기

세 수의 합이 0이어야 하므로, nums[i]를 하나 고정하면 나머지 두 수는 다음 조건을 만족해야 한다.

nums[j] + nums[k] = -nums[i]

즉, 3Sum 문제는 "하나의 값을 고정한 뒤, 나머지 구간에서 Two Sum을 푸는 문제"로 볼 수 있다.

이 관점에서 먼저 떠올릴 수 있는 방법은 HashSet을 사용하는 것이다. 그리고 배열을 정렬하면 같은 아이디어를 투 포인터 방식으로도 풀 수 있다.

풀이 1. HashSet으로 Two Sum처럼 풀기

아이디어

nums[i]를 하나 고정한 뒤, i + 1부터 끝까지 순회하면서 현재 값 nums[j]와 함께 합이 0이 되는 값을 찾는다.

이때 필요한 나머지 값은 다음과 같이 구할 수 있다.

int target = -nums[i] - nums[j];

만약 이전에 지나온 값 중 target이 있다면 다음 식이 성립한다.

nums[i] + target + nums[j] = 0

여기서 seen에는 현재 i를 기준으로 이미 지나온 값만 저장한다. 현재 nums[j]를 검사하기 전에 seen에서 target을 찾고, 검사가 끝난 뒤 nums[j]를 seen에 넣는다.

if (seen.contains(target)) {
    // triplet 발견
}

seen.add(nums[j]);

이 순서를 지키면 현재 값을 자기 자신과 다시 사용하는 일을 피할 수 있다. target은 이미 지나온 값이고, nums[j]는 현재 값이므로 서로 다른 인덱스에서 온 값이 된다.

중복 처리

이 문제는 중복된 트리플렛을 결과에 포함하면 안 된다. 그래서 먼저 배열을 정렬한다.

Arrays.sort(nums);

정렬하면 같은 값들이 연속해서 모이기 때문에 중복 처리가 쉬워진다.

먼저 기준값 nums[i]가 이전 값과 같다면 이미 같은 기준값으로 확인한 적이 있으므로 건너뛴다.

if (i > 0 && nums[i] == nums[i - 1]) {
    continue;
}

또한 정렬된 배열에서 nums[i]가 양수가 되는 순간 이후 세 수의 합은 0이 될 수 없다. 오른쪽 값들도 모두 nums[i] 이상이기 때문이다.

if (nums[i] > 0) {
    break;
}

트리플렛을 찾은 뒤에는 같은 nums[j] 값이 이어지는 경우를 건너뛴다. 같은 기준값과 같은 nums[j]를 다시 사용하면 동일한 트리플렛이 중복으로 추가될 수 있기 때문이다.

while (j + 1 < nums.length && nums[j] == nums[j + 1]) {
    j++;
}

코드

import java.util.*;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        /*
         * 하나의 값 nums[i]를 고정한 뒤,
         * 나머지 구간에서 HashSet으로 두 수를 찾는다.
         *
         * target이 seen에 있으면
         * nums[i] + target + nums[j] = 0 이다.
         *
         * 시간 복잡도: O(n^2)
         * 공간 복잡도: O(n)
         */

        Arrays.sort(nums);

        List<List<Integer>> answer = new ArrayList<>();

        for (int i = 0; i < nums.length - 2; i++) {
            // 같은 기준값은 한 번만 사용한다.
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            // 기준값이 양수라면 이후 세 수의 합은 0이 될 수 없다.
            if (nums[i] > 0) {
                break;
            }

            Set<Integer> seen = new HashSet<>();

            for (int j = i + 1; j < nums.length; j++) {
                int target = -nums[i] - nums[j];

                if (seen.contains(target)) {
                    answer.add(Arrays.asList(nums[i], target, nums[j]));

                    // 같은 nums[j] 값으로 동일한 트리플렛이 다시 추가되는 것을 막는다.
                    while (j + 1 < nums.length && nums[j] == nums[j + 1]) {
                        j++;
                    }
                }

                seen.add(nums[j]);
            }
        }

        return answer;
    }
}

풀이 2. 정렬과 투 포인터로 풀기

HashSet 풀이에서 투 포인터로 이어지는 이유

HashSet 풀이도 시간 복잡도는 O(n^2)이다. 하지만 중복 처리를 위해 이미 배열을 정렬하고 있다면, 정렬된 배열의 특성을 더 활용할 수 있다.

정렬된 배열에서는 왼쪽 포인터를 오른쪽으로 옮기면 값이 커지고, 오른쪽 포인터를 왼쪽으로 옮기면 값이 작아진다.

따라서 nums[i]를 고정한 뒤, 그 오른쪽 구간에서 left와 right를 양 끝에 두고 합을 조절할 수 있다.

 

현재 세 수의 합을 sum이라고 하면 경우는 세 가지다.

sum == 0  -> 정답에 추가
sum < 0   -> 합을 키워야 하므로 left를 오른쪽으로 이동
sum > 0   -> 합을 줄여야 하므로 right를 왼쪽으로 이동

배열이 정렬되어 있기 때문에 가능한 방식이다. 합이 작으면 더 큰 값을 사용해야 하므로 left를 오른쪽으로 옮기고, 합이 크면 더 작은 값을 사용해야 하므로 right를 왼쪽으로 옮긴다.

 

이렇게 하면 별도의 HashSet 없이도 나머지 두 수를 찾을 수 있다.

중복 처리

투 포인터 풀이에서도 같은 기준값 nums[i]는 한 번만 사용해야 한다.

if (i > 0 && nums[i] == nums[i - 1]) {
    continue;
}

그리고 정답을 찾은 뒤에는 left와 right를 한 칸씩 이동시킨다.

left++;
right--;

이후 같은 값이 이어지는 동안 계속 건너뛴다. 같은 left 값이나 같은 right 값을 다시 사용하면 동일한 트리플렛이 중복으로 추가될 수 있기 때문이다.

while (left < right && nums[left] == nums[left - 1]) {
    left++;
}

while (left < right && nums[right] == nums[right + 1]) {
    right--;
}

코드

import java.util.*;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        /*
         * 하나의 값 nums[i]를 고정한 뒤,
         * 나머지 구간에서 투 포인터로 두 수를 찾는다.
         *
         * 배열이 정렬되어 있으므로
         * 합이 작으면 left를 오른쪽으로 이동하고,
         * 합이 크면 right를 왼쪽으로 이동한다.
         *
         * 시간 복잡도: O(n^2)
         * 공간 복잡도: O(1)
         */

        Arrays.sort(nums);

        List<List<Integer>> answer = new ArrayList<>();

        for (int i = 0; i < nums.length - 2; i++) {
            // 같은 기준값은 한 번만 사용한다.
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            // 기준값이 양수라면 이후 세 수의 합은 0이 될 수 없다.
            if (nums[i] > 0) {
                break;
            }

            int left = i + 1;
            int right = nums.length - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                if (sum == 0) {
                    answer.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    left++;
                    right--;

                    // 같은 left 값은 동일한 트리플렛을 만들 수 있으므로 건너뛴다.
                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }

                    // 같은 right 값은 동일한 트리플렛을 만들 수 있으므로 건너뛴다.
                    while (left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }

        return answer;
    }
}

복잡도

HashSet 풀이

HashSet 풀이에서는 먼저 배열을 정렬하는 데 O(n log n)이 걸린다. 이후 바깥 반복문에서 하나의 값을 고정하고, 안쪽 반복문에서 나머지 구간을 순회하므로 O(n^2)이 걸린다.

따라서 전체 시간 복잡도는 다음과 같다.

O(n log n + n^2) = O(n^2)

공간 복잡도는 seen에 저장되는 값의 개수 때문에 O(n)이다. seen은 바깥 반복문마다 새로 만들어지므로 누적해서 O(n^2)이 되지는 않지만, 한 번에 최대 O(n)개의 값을 저장할 수 있다.

투 포인터 풀이

투 포인터 풀이도 정렬에 O(n log n)이 걸린다. 이후 각 i마다 left와 right가 한 방향으로만 이동하므로 내부 탐색은 O(n)이다. 이를 바깥 반복문에서 최대 n번 수행하므로 전체 시간 복잡도는 O(n^2)이다.

O(n log n + n^2) = O(n^2)

공간 복잡도는 추가로 사용하는 자료구조가 없기 때문에 O(1)로 볼 수 있다.

 

두 풀이를 비교하면 다음과 같다.

HashSet 풀이
- 시간 복잡도: O(n^2)
- 추가 공간 복잡도: O(n)

투 포인터 풀이
- 시간 복잡도: O(n^2)
- 추가 공간 복잡도: O(1)

정리

3Sum 문제는 세 수를 모두 직접 고르면 O(n^3)이 되기 때문에 비효율적이다. 이를 개선하기 위해 하나의 값을 고정하고, 나머지 두 수를 찾는 문제로 바꿀 수 있다.

 

이 관점에서 먼저 생각할 수 있는 방법은 HashSet을 이용한 Two Sum 방식이다. 현재 값과 합쳐서 0을 만들 수 있는 값을 seen에서 찾으면 되므로 직관적으로 이해하기 쉽다.

 

여기서 한 단계 더 나아가면 투 포인터 풀이로 이어진다. 중복 처리를 위해 배열을 정렬했다면, 정렬된 배열에서 왼쪽 포인터와 오른쪽 포인터를 움직이며 합을 조절할 수 있다.

 

결과적으로 두 풀이 모두 시간 복잡도는 O(n^2)이다. 다만 HashSet 풀이는 O(n)의 추가 공간을 사용하고, 투 포인터 풀이는 별도의 자료구조 없이 O(1)의 추가 공간으로 해결할 수 있다. 그래서 이 문제에서는 정렬 후 투 포인터 방식이 더 깔끔한 풀이로 볼 수 있다.

스터디 2주차 회고

예전에는 어렵지 않게 풀 수 있었던 문제들도 최근에는 바로바로 떠오르지 않는 경우가 많았다. AI에 너무 의존하다 보니 스스로 생각하는 시간이 줄어들었고, 그만큼 문제를 붙잡고 고민하는 힘도 조금 약해진 것 같다.

 

남은 스터디 기간에는 풀이 개수보다도 스스로 생각하는 시간을 조금 더 늘리는 것을 목표로 해야겠다.