15. 3Sum

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

3Sum - LeetCode

배열에서 원소를 3개 뽑아서 합이 0이 되는 조합을 중복 없이 모두 찾는 문제.

풀이 1 - DFS

아이디어

조금만 더 생각을 해봤다면 시도하지 않았을 방법이다...

DFS를 이용해서 만들 수 있는 3개의 원소 조합을 모두 확인했다.

그리고 Time Limit Exceeded...

코드

function threeSum(nums: number[]): number[][] {
    const answerSet = new Set < string > ();
    const answer: number[][] = [];

    function dfs(start: number, path: number[]) {
        if (path.length === 3) {
            const sum = path.reduce((a, b) => a + b, 0);
            if (sum === 0) {
                const sorted = [...path].sort((a, b) => a - b);
                const key = sorted.join(',');
                if (!answerSet.has(key)) {
                    answerSet.add(key);
                    answer.push(sorted);
                }
            }
            return;
        }

        for (let idx = start; idx < nums.length; idx++) {
            dfs(idx + 1, [...path, nums[idx]]);
        }
    }

    dfs(0, []);
    return answer;
};

시간 / 공간 복잡도

시간 복잡도: n개의 원소 중에서 3개를 뽑는 조합의 개수는 n(n-1)(n-2)/6 = n³/6 - n²/2 + n/3 이므로, n이 충분히 크면 O(n³)
공간 복잡도: 만들 수 있는 조합이 모두 합이 0이 되는 정답이라면 answerSet에 모든 조합이 저장되어야 하므로 최악의 경우 O(n³)

풀이 2 - Hash map

아이디어

힌트와 문제를 찬찬히 살펴보니 이 문제는 Two Sum 문제와 매우 유사하다! x + y + z = 0 이 되는 원소 조합을 구한다고 생각했을 때, y + z = -x인 y, z의 조합을 구해주는 문제로 바꾸어 줄 수 있다.

Two Sum에서 풀었던 것과 비슷하게 Set을 이용해서 중복을 확인해주는 방식을 사용했다.

매 반복마다 set을 만들고 triplet을 정렬하고 join해서 중복을 확인하는 자잘한 작업들이 시간이 많이 걸리지 않을까? 했는데 역시나 Time Limit Exceeded 결과가 나왔다.

코드

function threeSum(nums: number[]): number[][] {
    const answerSet = new Set < string > ();
    const answer: number[][] = [];

    for (let xIdx = 0; xIdx < nums.length - 2; xIdx++) {
        const x = nums[xIdx];
        const set = new Set < number > ()

        for (let yIdx = xIdx + 1; yIdx < nums.length; yIdx++) {
            const z = -x - nums[yIdx];
            if (set.has(z)) {
                const triplet = [x, nums[yIdx], z].sort((a, b) => a - b);
                const key = triplet.join(',');
                if (!answerSet.has(key)) {
                    answerSet.add(key);
                    answer.push(triplet);
                }
            }
            set.add(nums[yIdx]);
        }
    }

    return answer;
};

시간 / 공간 복잡도

시간 복잡도: x를 순회하는 반복 안에 y를 순회하는 반복이 있으므로 O(n²). z를 찾는 것은 평균적으로 O(1)이다.
공간 복잡도: O(n²)일까? 아니면 O(n³)일까...? (아직 의문)

풀이 3 - 투포인터

아이디어

조합을 정렬하고, set을 이용해서 중복을 확인하는 과정에서 시간이 오래 걸린다는 것은 짐작했는데 다른 풀이 방법이 떠오르지 않아서 GPT의 도움을 받아... 투포인터로 풀었다.

어떤 때에 투포인터 방식을 떠올려야 하는지는 아직 잘 모르겠다.

코드

function threeSum(nums: number[]): number[][] {
    const result: number[][] = [];
    nums.sort((a, b) => a - b);

    for (let idx = 0; idx < nums.length - 2; idx++) {
	    // 같은 숫자로 시작하는 조합을 제거 (시도하지 않는다)
        if (idx > 0 && nums[idx] === nums[idx - 1]) continue;

        let left = idx + 1;
        let right = nums.length - 1;

        while (left < right) {
            const sum = nums[idx] + nums[left] + nums[right];

            if (sum === 0) {
                result.push([nums[idx], nums[left], nums[right]]);
                // 중복된 조합을 제거하기 위해서 같은 원소인 경우를 건너뛴다.
                while (left < right && nums[left] === nums[left + 1]) {
                    left++;
                }
                while (left < right && nums[right] === nums[right - 1]) {
                    right--;
                }
                // 다음 조합을 시도하기
                left++;
                right--;
                continue;
            }
            if (sum < 0) {
                left++;
                continue;
            }
            right--;
        }
    }

    return result;
}

시간 / 공간 복잡도

시간 복잡도: idx를 순회하는 데 O(n), 반복 내부에서 투포인터로 탐색하는 데 O(n)이므로 O(n²)
공간 복잡도: left, right 포인터를 제외한 추가 공간은 필요하지 않으므로 O(1)