LeetCode 15 - 3Sum · codetosoul

이 문제는 정수 배열에서 합이 0이 되는 서로 다른 세 수의 조합을 찾는 문제다. 난이도는 Medium이고, 단순히 삼중 루프로 모든 조합을 확인하면 시간복잡도가 O(n³)까지 커지기 때문에, 하나의 값을 먼저 고정한 뒤 나머지 구간을 two-sum 문제처럼 처리했다.

문제 링크 & 설명

문제 링크: 15. 3Sum
요약: 정수 배열 nums가 주어졌을 때, 세 수의 합이 0이 되는 모든 unique triplet을 반환하는 문제.

예를 들어 입력이 이렇게 주어진다고 해보자.

nums = [-1, 0, 1, 2, -1, -4]

합이 0이 되는 조합은 다음과 같다.

[-1, -1, 2]
[-1, 0, 1]

문제에서 원하는 것은 인덱스 조합이 아니라 값의 조합이다. 같은 값 조합이 여러 번 만들어질 수 있으므로, 중복 triplet을 제거하는 처리가 필요하다.

접근 방법

1. 하나의 값을 먼저 고정하기

3Sum은 세 수를 골라야 하지만, 하나의 값을 먼저 고정하면 남은 문제는 two-sum과 같은 형태가 된다.

예를 들어 현재 고정한 값이 -1이라면, 나머지 두 수의 합은 1이어야 한다.

fixed = -1
target = 1

그러면 고정한 값 뒤쪽 구간을 순회하면서, 현재 값과 더했을 때 target이 되는 보완값을 찾으면 된다. 이때 이미 본 값을 hash map에 저장해두면, 필요한 보완값이 있었는지 평균 O(1)에 확인할 수 있다.

target = -nums[i]
nums_map = {}

for j in range(i + 1, n):
    comp = target - nums[j]
    if comp in nums_map:
        answer.add((nums[i], comp, nums[j]))
    nums_map[nums[j]] = j

2. 먼저 정렬하는 이유

이 풀이에서는 배열을 먼저 정렬했다. 정렬을 해두면 바깥쪽 반복문에서 같은 값을 다시 고정하지 않도록 건너뛸 수 있고, triplet을 set에 넣을 때도 값의 순서가 일정하게 유지된다.

nums.sort()

for i in range(n - 2):
    if i > 0 and nums[i] == nums[i - 1]:
        continue

예를 들어 -1이 여러 번 있어도 바깥쪽 고정값으로는 첫 번째 -1만 사용한다. 그렇지 않으면 같은 시작값으로 같은 조합을 다시 만들 가능성이 커진다.

3. set으로 중복 triplet 제거하기

바깥쪽 중복은 건너뛰더라도, 안쪽 구간에 같은 값이 여러 개 있으면 같은 triplet이 다시 만들어질 수 있다. 그래서 결과를 바로 list에 넣지 않고, tuple 형태로 set에 넣었다.

answer.add((nums[i], comp, nums[j]))

정렬된 배열을 순회하고 있기 때문에 tuple 안의 값 순서도 일정하게 들어간다. 마지막에는 LeetCode 반환 형식에 맞춰 tuple을 list로 바꿔준다.

return [list(triplet) for triplet in answer]

4. two-pointer 아이디어

풀이를 찾아보면서 정렬 후 two-pointer를 쓰는 방식도 같이 공부했다. 하나의 값을 고정하는 점은 같지만, 나머지 두 값을 hash map으로 찾는 대신 left와 right 포인터를 양쪽 끝에 두고 합을 비교한다.

합이 0보다 작으면 더 큰 값이 필요하므로 left를 오른쪽으로 옮기고, 합이 0보다 크면 더 작은 값이 필요하므로 right를 왼쪽으로 옮긴다. 합이 0이면 triplet을 저장한 뒤, 같은 값이 반복되지 않도록 left와 right를 중복 값 너머로 이동시킨다. 코드 예시는 실제 구현 코드 아래에 따로 정리했다.

트러블 슈팅

이 문제에서 가장 신경 써야 하는 부분은 중복 처리다. 3Sum은 정답이 하나가 아니라 여러 triplet이고, 같은 값 조합은 한 번만 반환해야 한다. 그래서 바깥쪽에서는 같은 고정값을 건너뛰고, 결과 저장에는 set을 사용했다.

다만 set을 사용하면 반환 순서는 보장되지 않는다. LeetCode에서는 triplet의 순서와 전체 결과의 순서를 요구하지 않기 때문에 이 방식이 가능하다. 만약 출력 순서까지 고정해야 하는 문제라면, 마지막에 별도 정렬을 하거나 two-pointer 방식에서 중복을 직접 건너뛰는 식으로 처리해야 한다.

복잡도 분석

시간 복잡도: O(n²)
- 정렬에는 O(n log n)이 걸리고, 바깥쪽 반복문마다 뒤쪽 구간을 한 번씩 순회한다. 전체적으로는 이중 반복이 지배하므로 O(n²)으로 정리한다.
공간 복잡도: O(n)
- hash map 풀이에서는 각 고정값마다 뒤쪽 구간에서 본 값을 저장하기 위한 hash map이 필요하다. 결과를 저장하는 set까지 포함하면 정답 개수에 비례하는 공간도 추가로 사용한다.
- two-pointer 풀이에서는 결과 배열을 제외하면 포인터와 합 계산에 필요한 변수만 사용하므로 추가 공간은 O(1)로 정리할 수 있다.

구현 코드

최종 코드는 배열을 정렬한 뒤, 하나의 값을 고정하고 나머지 구간을 two-sum처럼 확인하는 방식이다.

from typing import Dict, Set

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        answer: Set[tuple[int, int, int]] = set()
        n = len(nums)
        nums.sort()

        for i in range(n - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            target = -nums[i]
            nums_map: Dict[int, int] = {}

            for j in range(i + 1, n):
                comp = target - nums[j]
                if comp in nums_map:
                    answer.add((nums[i], comp, nums[j]))
                nums_map[nums[j]] = j

        return [list(triplet) for triplet in answer]

추가로 공부한 two-pointer 코드

풀이를 찾아보면서 확인한 two-pointer 방식은 다음과 같다. 이 방식도 먼저 하나의 값을 고정하지만, 남은 구간에서는 hash map을 만들지 않고 left와 right 포인터를 움직이면서 합을 맞춘다.

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        answer = []

        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            left = i + 1
            right = len(nums) - 1

            while left < right:
                total = nums[i] + nums[left] + nums[right]

                if total == 0:
                    answer.append([nums[i], nums[left], nums[right]])

                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1

                    left += 1
                    right -= 1
                elif total < 0:
                    left += 1
                else:
                    right -= 1

        return answer

시간복잡도는 hash map 방식과 같은 O(n²)이다. 대신 매 반복마다 별도 hash map을 만들지 않기 때문에, 결과 배열을 제외한 추가 공간은 포인터 몇 개뿐이다. 중복 처리를 직접 해줘야 해서 코드가 조금 더 길어지지만, 3Sum의 표준 풀이로는 two-pointer 방식이 더 자주 쓰인다.

요약 및 회고

3Sum은 세 수를 한 번에 찾으려고 하면 조합 수가 커진다. 하나의 값을 먼저 고정하면 남은 두 수는 two-sum 문제로 바뀌고, hash map을 사용해서 필요한 값을 빠르게 확인할 수 있다.

이번 풀이에서는 정렬로 고정값 중복을 줄이고, set으로 결과 중복을 제거했다. hash map 방식은 two-sum에서 확장되는 흐름을 확인하기 좋고, two-pointer 방식은 추가 공간을 줄이면서 중복을 직접 처리하는 표준 풀이로 정리할 수 있다.