[LeetCode] - 세 수의 합

문제) 배열의 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력해라 

https://leetcode.com/problems/3sum/description/

3Sum - LeetCode

---

풀이) 

1.브루트 포스 

먼저 브루트포스로 풀이했다. 이때 중복되는 값일 경우에는 무시하도록 continue 해주었다. 

 

▶ [ -4 , -4 , 1 , 2 , ... , 1 ] 일 경우에 -4 다음에 다시 -4가 나오면서 결과가 중복되므로 이 경우에는 무시하고 넘어가도록 해준다는 의미이다. 

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

        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:
                        result.append([nums[i], nums[j], nums[k]])
        
        
        return result

 

다만 이렇게 부르트포스로 풀게되면 Time Limit Exceeded를 맞이할 수 있다. 

 

2. 투 포인터 접근 

그렇다면 다른 방법을 생각해보자. 합을 0으로 만드는 인덱스가 아닌 값을 반환하므로 투 포인터를 사용할 수 있을 것이라 생각된다.  아래와 같은 원리로 생각하여 풀이를 했다. 

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = []
        #오름차순 정렬 
        nums.sort()

        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] 
                #만일 sum이 0보다 클 경우 좌측으로 한 칸 
                if sum > 0 :
                    right -= 1 
                #만일 sum이 0보다 작을 경우 우측으로 한 칸 
                elif sum < 0 :
                    left += 1
                #sum이 0일 경우 해당 값 append
                else :
                    result.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
                    right -= 1 
                    left += 1

        return result