문제
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 resultnums[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] 로 따라가 보면 다음과 같다.
i = 0(값-2):lo가 오른쪽으로 가다가[-2, 0, 2]를 찾는다. 답을 찾았으므로lo와hi를 둘 다 옮겨hi는 위치 3 (값0) 이 된다.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] 다.
i | lo | hi | 세 수 | 동작 | |
|---|---|---|---|---|---|
| 0 | 1 | 5 | -4, -1, 2 | -3 | lo 오른쪽 |
| 0 | 2 | 5 | -4, -1, 2 | -3 | lo 오른쪽 |
| 0 | 3 | 5 | -4, 0, 2 | -2 | lo 오른쪽 |
| 0 | 4 | 5 | -4, 1, 2 | -1 | lo 오른쪽, 구간 끝 |
| 1 | 2 | 5 | -1, -1, 2 | 0 | 기록, 둘 다 옮김 |
| 1 | 3 | 4 | -1, 0, 1 | 0 | 기록, 둘 다 옮김, 구간 끝 |
| 2 | nums[2] == nums[1] 이라 건너뜀 | ||||
| 3 | 4 | 5 | 0, 1, 2 | 3 | hi 왼쪽, 구간 끝 |
i = 2 를 건너뛰지 않았다면 구간 [3, 5] 에서 [-1, 0, 1] 이 한 번 더 기록됐을 것이다.