15. 3Sum

예전에 풀었던 2Sum에 이은 3Sum문제..

 

a + b + c = 0이 되는 조합을 출력하는 것이고, 중복 조합은 허락하지 않는다. 

중복을 허락하지 않으므로, set으로 결과 관리를 하면 될것 같음

n^3으로 풀릴것도 같다. 

 

1) 첫번째 도전 (for문 3번)

def threeSum(self, nums: List[int]) -> List[List[int]]:
        ans = []
        nums.sort()
        check = set()
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                for k in range(j+1, len(nums)):
                    a, b, c, = nums[i], nums[j], nums[k]
                    if a+b+c == 0 and (a,b,c) not in check:
                        ans.append([a,b,c])
                        check.add((a,b,c))
        return ans

=> 결과는 Time Limit이다. 

 

n^3을 n^2으로 줄이는 방법을 생각해야된다. 

 

2) two sum에서 사용했던 방법중에 in을 사용하는 방법이 있었다. 

=> 결과는 틀린 답..중간에 자꾸 하나씩 답이 빠진다. 

=> sum값이 0일때 left, right를 하나씩 증가,감소시키는데, 그 다음에 답이 있는 경우에 문제가 생김

    def threeSum(self, nums):
        ans = []
        nums.sort()
        check = set()

        left, right = 0, len(nums)-1

        #2개 이하는 값을 만들 수 없으므로 빈 리스트
        if len(nums) < 3: return []


        while left<right:
            sum = nums[left] + nums[right]

            if sum == 0:
                if 0 in nums[left+1: right]:
                    tmp = [0, nums[left], nums[right]]
                    tmp.sort()
                    if tmp not in ans:
                        ans.append(tmp)
				left += 1
                right -= 1
            elif sum < 0:
                if (sum * -1) in nums[left+1: right]:
                    tmp = [sum*(-1), nums[left], nums[right]]
                    tmp.sort()
                    if tmp not in ans:
                        ans.append(tmp)
                left += 1
            elif sum > 0:
                if (sum * -1) in nums[left+1: right]:
                    tmp = [sum*(-1), nums[left], nums[right]]
                    tmp.sort()
                    if tmp not in ans:
                        ans.append(tmp)
                right -= 1
        print(ans)
        return ans

3) 기준을 하나로 두고, 나머지를 two pointer로 움직이는 방식

-> a+b+c = 0을 만들기 위해서는 최소 3개의 수가 필요하다. 

    for문도 n-2번까지만 돌면 된다

-> 중복 체크도 하면 시간이 더 줄어들 수 있다. (arr[i] == arr[i+1] 이면 continue)

-> 어렵다..이걸 다들 어떻게 푸냐..책보고 공부하는거지만 어려움

def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 3개 이하는 조건이 성립이 안되므로 패스
        if len(nums) < 3: return []
        result = []
        # 정렬해서 구하도록 변경
        nums.sort()
        
        # 전체 크기의 -2까지만 돌리도록...
        for i in range(len(nums)-2):
            # 바로 전에 구한 값이므로 패스 
            if i>0 and nums[i] == nums[i-1]:
                continue
            
            # i라는 기준에서 i다음 것과 배열의 끝값을 기준으로 two pointer를 설정한다. 
            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
                elif sum == 0:
                    # append시에 정렬되도록 순서대로 넣자
                    tmp = [nums[i], nums[left], nums[right]]
                    if tmp not in result:
                        result.append(tmp)
                    
                    # 같은 값이면 건너뛰도록...중복 허용하지 않는 방법
                    if left < right and nums[left] == nums[left+1]:
                        left+=1
                    elif left < right and nums[right] == nums[right-1]:
                        right-=1
                    left += 1
                    right -=1
        return result