- 문제 이해
숫자 배열 nums가 주어질 때 i != j != k 3개 숫자를 더해
0을 만들 수 있는 경우의 수를 2차원 배열로 반환하면 되는 문제입니다.
인덱스가 서로 다른 3개 숫자라는 뜻이죠?
주의할 것은 3개 숫자가 모두 중복되는 답은 안된다는 점입니다.
첫번째 예제를 보면 알 수 있죠?
더해서 0 이 나올 수 있는 i != j != k의 경우의 수는
[[-1, 0, 1], [0, 1, -1], [-1, 2, -1]] 3개이지만
첫번째와 두번째 배열의 3개 숫자가 모두 겹칩니다.
그래서 답은 [[-1, -1, 2], [ -1, 0, 1]] 두개만 나오는 겁니다.
- 풀이 과정
일단 완전 탐색으로 풀린다면 완전 꿀인 문제죠??
시간복잡도부터 냅다 생각해봅니다.
리스트에서 3개의 요소를 중복 없이 뽑으려면 O(nC3) 다른 말로는 O(n^3)입니다.
제약 조건을 보면 nums 의 길이는 3000까지 나올 수 있습니다.
혹시나 궁금한데 생각하기 귀찮으신 분들을 위해 말씀드리면 3000^3은
27,000,000,000 즉, 270억입니다.
세상은 여전히 차갑기만 합니다.
이제 다른 방법을 모색해봐야 하는데, 놀랍게도 문제를 뚫어져라 쳐다보니 힌트를 얻었습니다.
위 설명에도 덧붙였던 첫번째 예제입니다.
보시면 앞에서부터 숫자 3개를 뽑아서 0을 만들었다면 인덱스 순서대로
[-1, 0, -1]이 먼저 나오고 그 다음에는 [-1, 2, -1]이 나와야 하는데,
출력을 보면 순서가 제멋대로죠?
배열의 순서가 바뀔 일.
다들 아시겠지만 sort 밖에 없겠죠?
그렇다면 왜 sort 를 하였는지 생각해보면 금새 떠올릴 수 있습니다.
이 문제는 완전 탐색으로는 풀지 못하는 문제였고,
정렬을 했다면 사용할 수 있는 O(N)짜리 귀여운 친구가 있습니다.
바로 투포인터죠.
정리하자면,
- 배열을 정렬한다.
- 첫번째 숫자는 for 문을 통해 순회하면서 정하고 두번째, 세번째 숫자는 각각 투포인터로 정한다.
- 숫자 3개가 중복되는 경우를 방지한다.
이렇게만 지키면 대강 O(n log n) + O(n^2) 정도 나올 것 같습니다.
제가 한번 구현해보겠습니다.
- 정답 코드
class Solution(object):
def threeSum(self, nums):
nums.sort()
ans = []
for i in range(len(nums)-2):
if i>0 and nums[i] == nums[i-1]:
# 첫번째 숫자가 이전 숫자와 같으면 continue (중복 방지)
continue
if nums[i]>0:
# 배열이 sort 되어 있기 때문에 첫 숫자가 0보다 커지면 끝 (최적화)
break
left = i+1
right = len(nums)-1
while left < right:
if nums[i]+nums[left] > 0:
break
s = nums[i] + nums[left] + nums[right]
if s==0:
ans.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]:
left+=1
# 두번째 숫자 중복 방지
while right > left and nums[right] == nums[right-1]:
right-=1
# 세번째 숫자 중복 방지
left+=1
right-=1
elif s>0:
right-=1
else:
left+=1
return ans