문제

LeetCode 15. 3Sum. 정수 배열 nums 에서 서로 다른 위치의 세 수를 골라 합이 0 이 되는 조합을 모두 반환한다. 같은 값 세 개로 이루어진 조합은 한 번만 넣는다. 제약은 3 ≤ len(nums) ≤ 3000 이다.

nums = [-1, 0, 1, 2, -1, -4] 이면 답은 다음 두 개다.

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

-1 이 배열에 두 번 있어서 [-1, 0, 1] 을 만드는 위치 조합은 두 가지다. 그래도 값이 같으므로 답에는 한 번만 넣는다. 이 문제에서 까다로운 부분은 합을 찾는 것보다 이 중복을 걸러내는 것이다.

세 수를 모두 고르면 느리다

위치 세 개를 모든 방법으로 고르고, 합이 0 인 것을 정렬해서 set 에 넣으면 답은 나온다. 하지만 n = 3000 이면 조합이 , 약 45 억 개라 시간 안에 끝나지 않는다.

풀이: 첫 수를 고정하고 투 포인터

배열을 먼저 정렬한다. 그다음 첫 수 nums[i] 를 하나 고정하면, 남은 문제는 “i 오른쪽 구간에서 합이 -nums[i] 인 두 수 찾기” 가 된다. 정렬된 구간에서 합이 정해진 두 수는 양 끝에서 안쪽으로 다가오는 포인터 두 개로 찾을 수 있다. 이런 방식을 투 포인터라고 한다.

정렬된 구간에서 두 수 찾기

구간 [i + 1, n - 1] 의 왼쪽 끝을 lo, 오른쪽 끝을 hi 로 두고 세 수의 합 를 본다.

기호뜻
고정한 첫 수의 위치
두 번째 수의 위치. 에서 시작해 오른쪽으로만 간다
세 번째 수의 위치. 에서 시작해 왼쪽으로만 간다
세 수의 합
  • 이면 lo 를 오른쪽으로 옮긴다. 지금 nums[lo] 를 남은 어떤 hi 와 짝지어도 nums[hi] 가 지금보다 작거나 같으므로 합이 0 보다 작다. 그래서 lo 위치는 이 i 의 답에 더는 쓰일 수 없다.
  • 이면 같은 이유로 hi 를 왼쪽으로 옮긴다.
  • 이면 답을 기록하고 lo 와 hi 를 둘 다 옮긴다. 이유는 아래 “합이 0 일 때 lo 와 hi 를 둘 다 옮기는 이유” 절에서 다룬다.

한 번 비교할 때마다 위치 하나를 버리므로, i 하나에 대해 구간 길이만큼만 비교한다. 첫 수가 개이므로 전체는 이고, 정렬의 은 여기에 묻힌다.

코드

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        n = len(nums)
        result = []
 
        for i in range(n - 2):
            if nums[i] > 0:
                break                                  # 남은 세 수가 모두 양수
            if i > 0 and nums[i] == nums[i - 1]:
                continue                               # 같은 첫 수는 한 번만
 
            lo, hi = i + 1, n - 1                      # i 마다 구간 전체에서 다시 시작
            while lo < hi:
                s = nums[i] + nums[lo] + nums[hi]
                if s < 0:
                    lo += 1
                elif s > 0:
                    hi -= 1
                else:
                    result.append([nums[i], nums[lo], nums[hi]])
                    lo += 1
                    hi -= 1
                    while lo < hi and nums[lo] == nums[lo - 1]:
                        lo += 1                        # 같은 두 번째 수는 한 번만
 
        return result

nums[i] > 0 에서 멈추는 것은 속도를 위한 것이다. 정렬돼 있으므로 첫 수가 양수면 뒤의 두 수도 양수라 합이 0 이 될 수 없다.

합이 0 일 때 lo 와 hi 를 둘 다 옮기는 이유

첫 수가 고정되면 두 수의 합은 -nums[i] 로 정해져 있다. 그래서 두 번째 수의 값이 정해지면 세 번째 수의 값도 하나로 정해진다.

답을 찾은 직후 lo 만 옮긴 경우를 생각해 보자.

  • nums[lo] 가 더 큰 값으로 바뀌었다면, nums[hi] 는 그대로이므로 합이 0 보다 크다. 답이 아니다.
  • nums[lo] 가 같은 값이라면(중복 원소), 방금 기록한 조합과 값이 같다. 중복이다.

어느 경우든 지금의 hi 와 짝지어서 새 답이 나오지 않는다. hi 만 옮기는 경우도 같은 이유로 지금의 lo 로는 새 답이 없다. 그래서 둘 다 옮겨도 놓치는 답이 없다. 한쪽만 옮겨도 다음 비교에서 결국 다른 쪽이 움직이지만, 그 사이에 같은 값이 남아 있으면 같은 조합이 한 번 더 기록된다.

i 마다 hi 를 끝으로 되돌리는 이유

hi = n - 1 을 for 문 바깥에 한 번만 두고 lo 만 i + 1 로 되돌리면 답을 놓친다. 정렬된 [-2, -1, -1, 0, 2] 로 따라가 보면 다음과 같다.

  1. i = 0 (값 -2): lo 가 오른쪽으로 가다가 [-2, 0, 2] 를 찾는다. 답을 찾았으므로 lo 와 hi 를 둘 다 옮겨 hi 는 위치 3 (값 0) 이 된다.
  2. i = 1 (값 -1): hi 를 되돌리지 않았으므로 위치 3 에서 시작한다. 값 2 가 있는 위치 4 는 구간 밖에 남아서 [-1, -1, 2] 를 찾지 못한다.

hi 를 왼쪽으로 옮긴 판단은 앞의 “정렬된 구간에서 두 수 찾기” 절에서 본 것처럼 “그때의 nums[i] 와 그때의 lo 로는 오른쪽 값이 짝이 될 수 없다” 는 것이었다. i 가 바뀌면 필요한 두 수의 합 -nums[i] 가 바뀌고, lo 도 i + 1 로 돌아가 다시 작은 값부터 본다. 그 판단의 근거가 둘 다 사라졌으므로, 오른쪽 값들을 다시 후보로 넣어야 한다. 첫 수마다의 탐색은 구간 [i + 1, n - 1] 전체에서 새로 하는 별개의 두 수 찾기다.

set 없이 중복 건너뛰기

정렬했으므로 값이 같은 원소는 서로 붙어 있다. 그리고 답 안의 세 수도 항상 작은 값부터 기록된다. 그래서 같은 값을 연달아 첫 수나 두 번째 수로 쓰지 않기만 하면 같은 조합이 두 번 나오지 않는다.

첫 수. nums[i] == nums[i - 1] 이면 건너뛴다. 앞의 같은 값으로 이미 구간 [i, n - 1] 을 훑었고, 지금 훑을 [i + 1, n - 1] 은 그 안에 들어 있다. 같은 값을 첫 수로 하는 답은 앞에서 모두 나왔다.

비교 대상을 다음 원소(nums[i] == nums[i + 1])로 바꾸면 안 된다. 그러면 같은 값의 첫 번째 원소를 건너뛰게 되고, 그 원소의 구간에 들어 있던 두 번째 같은 값을 쓸 수 없다. [-1, -1, 2] 에서 첫 -1 을 건너뛰면 남은 [-1, 2] 에서 세 수를 고를 수 없어 답이 빈 목록이 된다.

두 번째 수. 답을 찾고 lo 를 옮긴 뒤, nums[lo] 가 방금 쓴 값과 같은 동안 계속 옮긴다. 세 번째 수는 따로 건너뛰지 않아도 된다. 첫 수가 고정돼 있으므로, 두 번째 수의 값이 바뀌면 필요한 세 번째 수의 값도 달라진다. 그래서 같은 nums[hi] 값은 분기에서 저절로 지나간다.

예제 따라가 보기

[-1, 0, 1, 2, -1, -4] 를 정렬하면 [-4, -1, -1, 0, 1, 2] 다.

ilohi세 수동작
015-4, -1, 2-3lo 오른쪽
025-4, -1, 2-3lo 오른쪽
035-4, 0, 2-2lo 오른쪽
045-4, 1, 2-1lo 오른쪽, 구간 끝
125-1, -1, 20기록, 둘 다 옮김
134-1, 0, 10기록, 둘 다 옮김, 구간 끝
2nums[2] == nums[1] 이라 건너뜀
3450, 1, 23hi 왼쪽, 구간 끝

i = 2 를 건너뛰지 않았다면 구간 [3, 5] 에서 [-1, 0, 1] 이 한 번 더 기록됐을 것이다.

References