3Sum

2026-03-10

---

오늘 내가 기록할 알고리즘은 NeetCode의 Two Pointer 문제이다.

인덱스의 3가지 수의 합이 0이 되어야 하는 모든 리스트를 리턴해야 하는데, 중복되는 수가 있으면 안된다.

 

처음 풀이는 brute force 방식으로 문제를 해결해 보았다.

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> list = new HashSet<>();
        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i++){
            for(int j = i + 1; j < nums.length; j++){
                for(int k = j + 1; k < nums.length; k++){
                    if(nums[i] + nums[j] + nums[k] == 0){
                        List<Integer> subList = Arrays.asList(nums[i], nums[j], nums[k]);
                        list.add(subList);
                    }
                }
            }
        }
        return new ArrayList<>(list);
    }
}

 

리턴 형식이 List임에도 불구하고 Set을 선택한 이유는 중복되는 값을 피하기 위해서다. 

제공받은 배열을 정렬함으로 인해서 우리는 중복되지 않는 값만 Set에 저장할 수 있다.

 

for문을 세 개 생성한 다음 루프를 돌면서 모든 경우의 수를 탐색한다. 

이때에 3개 수의 합이 0이라면 해당 값을 리스트로 저장해 Set에 보관한다.

루프가 종료되면 Set Collection을 리스트의 파라미터로 넣어서 리턴한다.

 

이 방법은 가장 간단하지만, 시간이나 공간적인 면에서 완전 효율적이라고 이야기하지 못한다.

 

따라서 우리는 Two Pointer를 활용해 해당 문제를 풀어보도록하겠다.

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int l = i + 1, r = nums.length - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum > 0) {
                    r--;
                } else if (sum < 0) {
                    l++;
                } else {
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    l++;
                    r--;
                    while (l < r && nums[l] == nums[l - 1]) {
                        l++;
                    }
                }
            }
        }
        return res;
    }
}

Brute Force 부분과 비슷한 점이라면 정렬을 우선적으로 해주는 것이다. 

정렬을 함으로 인해서 중복된 수가 저장되는 걸 방어할 수 있다. 

 

우선적으로 세 개의 수 중에 하나의 인덱스 값은 고정으로 두고,

나머지 두 개의 값을 투포인터를 이용해 찾는 것이다.

그리고 만약 고정한 인덱스의 값이 0보다 크다면,

즉 양수라면 세 개의 합이 0을 넘을 수 밖에 없다는 뜻이기에 반복문을 종료하고 값을 리턴한다. 

 

투포인터의 인덱스 값은 고정된 인덱스 보다 1 큰 값과 뒤에서 마지막 인덱스를 둔다.

while문에서 만약 세 수의 합이 0보다 크다면 0에 가까운 값으로 만들기 위해 오른쪽 인덱스를 감소시키고

0보다 작다면 왼쪽 인덱스의 값을 증가시킨다.

 

만약 세 개의 합이 0이라면, 리스트에 저장하고 왼쪽과 오른쪽의 인덱스를 이동시켜준다. 

조건문 내에 있는 while 반복문은 중복된 값이 들어가는지 확인하는 로직으로서

만약 왼쪽 현재 인덱스 위치와 이전 왼쪽 인덱스 값과 동일할 경우 왼쪽 인덱스를 증가하도록 하였다.

 

---

 

투 포인터 문제를 풀면서 세 개의 합을 어떻게 투 포인터로 구현하지라는 고민도 되었고,

중복된 값을 걸려내기 위해 왼쪽 인덱스는 증가하면서

오른쪽 인덱스는 반복문을 사용하지 않는 것에 대해 의문을 가지게 되었다. 

 

일단 세 개의 합을 구현할 때에 하나의 인덱스를 고정으로 두게 되면

투 포인터로 구현이 가능하다는 것을 알게 되었고,

왼쪽 인덱스만 증가시켜도 중복된 값이 들어갈 수 없다는 것을 알게 되었다.