“파이썬 알고리즘 인터뷰” + https://leetcode.com/problems/3sum/
합이 0이 되는 배열의 요소 3개의 조합을 리스트로 출력하는 문제다.
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
역시나 바로 떠오르는 방법은 O(n^3)의 3중 반복문이다. 기본적인 방법이지만 문제에서 바라는 것은 그것보다는 빠른 방법일테다. 풀이에서는 투 포인터(정의된 이름은 아니지만 실전적인 풀이 기법이라고 한다.) 방식이 나오는데 이전 문제부터 계속해서 등장하고 있다. 개념이 아직 잡히지는 않았지만 따라서 풀어볼 수 밖에. 이 방식대로라면 O(n^2)의 복잡도가 된다. 도입부에서 리스트를 정렬하는 O(n log n)도 있지만.
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
results = []
nums.sort()
# 1. blute force
# for i in range(len(nums) - 2):
# if i > 0 and nums[i] == nums[i - 1]:
# continue
# for j in range(i + 1, len(nums) - 1):
# if j > i + 1 and nums[j] == nums[j - 1]:
# continue
# for k in range(j + 1, len(nums)):
# if k > j + 1 and nums[k] == nums[k - 1]:
# continue
# if nums[i] + nums[j] + nums[k] == 0:
# results.append([nums[i], nums[j], nums[k]])
# 2. two pointer
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, len(nums) - 1
while left < right:
sum = nums[i] + nums[left] + nums[right]
if sum < 0:
left += 1
elif sum > 0:
right -= 1
else:
results.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
return results투 포인터로 양 끝에서부터 안쪽으로 좁혀가며 답을 찾는다. 중복 값이 포인터의 앞뒤에 있다면 continue로 생략하는 것처럼 인덱스 실수를 하기 쉽겠다. 따라서 적어보면 이해가 가지만, 모르는 상태에서 고민을 계속한다고 이런 해결 방법이 도출될까. 그것도 훈련이겠다만.