[LeetCode_15] 세 수의 합

파이썬으로 배우는 알고리즘 책을 공부하며 풀었던 LeetCode문제들을 재정리해보자.

 

# 문제 설명 

15번  3Sum은 배열을 입력받아 합으로 0을 만들 수 있는 3개의 요소를 출력하는 문제이다.

단 결과에 중복된 요소 집합이 포함되면 안 된다.

Example

위 문제를 풀려고 시도했지만 시간 초과로 떴고, 다른 방법은 생각나지 않아 우선 책 풀이를 참고하였다.

 

# 시도 1 (Time Limit Exceeded) - 3중 for문

...당연히 시간 초과로 뜸.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        
        result =[]
        
        nums.sort()
        len_nums = len(nums)
        
        print(nums)
        
        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

중복된 쌍이 결과에 포함되지 않도록 하기 위해 if문으로 이전 인덱스 값이랑 같은지 여부에 따라 continue를 써서 구분을 하였다. 

 

# 풀이방법 1 - 투 포인터로 합 계산 (책 풀이 참고)

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
            
            # 투 포인터로 간격을 좁혀가며 합 sum 계산 
            left, right = i+1, len(nums) - 1
            
            while left < right :
                sum = nums[i] + nums[left] + nums[right]
                
                if sum > 0 :
                    right -= 1
                elif sum < 0 :
                    left += 1
                else : # sum이 0인 경우
                    result.append([nums[i], nums[left], nums[right]])
                    
                    # 양 옆으로 동일한 값이 있을 수도 있으니 skip
                    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

1. 첫 번째 인자는 for문으로 접근 (이때 중복된 값이 포함되지 않도록 if/continue 사용)

2. 두 번째와 세 번째 인자는 투 포인터를 이용하여 간격을 좁혀가며 sum이 0인 값을 찾는다.

  - 합이 0보다 크면 right -=1 로 값을 줄이고, 0보다 작으면 left+=1하여 값을 늘린다.

  - 만약 합이 0이라면, 양 옆으로 동일한 값은 skip하도록 처리한다. 

 

 

| 핵심 |

# 중복된 값은 건너뛰기
            if i > 0 and nums[i] == nums[i-1]:
                continue

 

# 투 포인터로 간격을 좁혀가며 합 sum 계산 
            left, right = i+1, len(nums) - 1
            while left < right :

 

# 양 옆으로 동일한 값이 있을 수도 있으니 skip
                    while left < right and nums[left] == nums[left + 1]:
                        left +=1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1

 

 

 

 

# 결과