[파이썬 알고리즘 인터뷰] - LeetCode 15. 3Sum (7장)

 

 

 

 

 

 

 

 문제

 

leetcode.com/problems/3sum/

3Sum - LeetCode

 

 

 

 

 

 

 문제 상황

 

- 세수의 합이 0이 되는 케이스를 찾는다.

 

 

 

 

 

 

 해결 전략

 

- Brute Force로 모든 경우를 순회하며 가능성을 찾으면 되지만 O(N^3)로 일반적 조건에서 속도 이슈가 발생할 수 밖에 없다.

 

- 투포인터를 활용해 한 요소를 기준으로 두 요소를 더해 그 합이 0보다 크면 줄이고, 0보다 작으면 키우는 방향으로 포인터를 이동시킨다.

 

- 이를 위해 사전에 정렬되어 있을 필요가 있다.

 

 

 

 

 

 

 코드

 

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = []
        nums.sort()
        # Brute Force O(N^3) -> 속도 이슈 발생
        # for i in range(len(nums)-2):
        #     for j in range(i+1,len(nums)-1):
        #         for k in range(j+1, len(nums)):
        #             if nums[i]+nums[j]+nums[k] == 0 : result.append([nums[i],nums[j],nums[k]])
        
        # 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:
                if nums[left] + nums[i] + nums[right] < 0: left += 1
                elif nums[left] + nums[i] + nums[right] > 0: right -= 1
                else : 
                    result.append([nums[i], nums[left], nums[right]]) # 이것으로 연산을 종료하면 while을 빠져나올 방법이 없어 무한루프
                    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 result

 

 

 

 

 

 

 

 

 해설

 

- 속도에 큰 차이가 안날 것 같지만 중복을 제거해주는 과정은 중요하다.

 

- 첫 요소를 이동시키며 그 요소의 오른쪽 두 값을 left, right로 지정해 합을 키우거나 줄이는 방향으로 이동시킨다.

 

 

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- 문제는 테스트케이스의 [0,0,0,0]에서 발생했는 데, 20, 21번째 줄의 중복을 제거하는 부분을 안 넣으면 답이 [0,0,0], [0,0,0]으로 같은 요소가 두번 나오게 된다. 하나의 답을 찾았을 때, 다음 찾는 답이 중복되지 않음을 확인해야 하는데, 답을 넣을 때 in 함수를 써도 되지만 그것보단 위의 방법이 더 빠르다

 

- 처음에는 18번째 줄에서 else에 답을 넣는 코드만 넣어 무한 루프에 빠졌다. 좀 더 엄밀한 정의가 필요하다.