3Sum

나의 논리

우선 시간초과를 받았다.
백준에서 비슷한 부분수열의 합 시리즈랑 유사해서 브루트 포스로 풀면 되겠구나 싶어서 재귀로 코드를 짰는데 시간초과가 났다.

def threeSum(self, nums: List[int]) -> List[List[int]]:
        
        if len(nums) < 3:
            return []
            
        import copy
        ret = set()
        nums.sort()
        
        def recursive(prev:int ,val:int, tempList:list):
            

            
            if len(tempList) == 3 and val == 0:
                ret.add(copy.deepcopy(tuple(tempList)))
                
            for i in range(prev+1, len(nums)):
                tempList.append(nums[i])
                recursive(i,val+nums[i],tempList)
                tempList.pop()
                
        tempList = []
        for i in range(len(nums)):
            tempList.append(nums[i])
            recursive(i,nums[i],tempList)
            tempList.pop()
        
        ret = [list(item) for item in ret ]
            
        
        return ret

threeSum 함수는 리트코드에서 기본 지정이기 때문에
나는 recursive라는 함수를 만들었다.
생각해보니 threeSum 함수 내부

for i in range(len(nums)):

여기서 O(n)

recursive 재귀의 깊이가 O(n)
또 한 recursive 재귀 호출스택에서

for i in range(prev+1, len(nums)):

반복문 때문에 O(n)
총 O(n^3) 시간복잡도를 가져서 시간초과가 났다.
(시간복잡도 틀리면 누가 댓글좀요...)

몰랐던 것

그리고 처음에는 계속 ret값이 None이거나 빈 리스트가 반환되길래 뭐지? 싶었더니 파이썬 특성때문이었다.

1

ret.add(copy.deepcopy(tuple(tempList)))

이 코드를 보면 깊은 복사를 했다.
파이썬에서 리스트를 복사할때 얕은 복사를 한다. 원본 리스트는 놔두고 리스트를 복사할때 변수들이 같은 리스트의 주소값을 가르킨다.
그래서 n번째 호출스택이 끝나고 n-1 번째 호출스택으로 돌아와
tempList를 pop 시켰을때 ret에 있는 원소도 pop되었다.
(같은 리스트의 주소값을 가르키기 때문에)
그래서 깊은 복사를 해줬다.

2

Set()에 리스트를 바로 add 하려고 하니 Hashable 에러가 떠서 보니 Set에는 해쉬가능한 변수만 넣을 수 있다고 하니..뭐 값을 바꿀 수 없는 원소만 넣을 수 있단다.
Tuple(tempList)를 Set()에 add 했다.

정답 논리

투포인터 배열의 임의의 두 원소를 가르키는 투 포인터로 O(n^2) 시간복잡도를 가지는 알고리즘이다.

def threeSum(self, nums: List[int]) -> List[List[int]]:
        
        ret = []
        nums.sort()

        for i in range(len(nums)):

            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:
                    ret.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 ret
        

투 포인터 전략은 배열이 정렬되어있을때 유용하다.

i로 첫번째 원소를 가르키면서
sum 값에 따라 left를 증가, right을 감소 시키면서
sum == 0일때마다 ret 리스트에 추가 해준다.

배열은 이미 정렬되어있고 또 중복된 값은 거르기때문에
결과 리스트에 중복된 배열이 들어 갈 일은 없다.