[파이썬 알고리즘 인터뷰] 9. 세 수의 합

 

 이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다.

 

 출처 : 파이썬 알고리즘 인터뷰

 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브

 

---

9. 세 수의 합

리트코드 15번 문제입니다.

leetcode.com/problems/3sum/

 

 

풀이

 책에서는 브루트포스, 투 포인터 풀이가 나와있습니다.

 핵심은 중복된 값을 건너뛰기를 구현하는 것입니다.

 

1. 브루트 포스 풀이

def threeSum(nums):
    result = []
    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 > 0 and nums[j] == nums[j-1]:
                continue
            for k in range(j+1,len(nums)):
                if k > 0 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

 중간 중간 중복된 값을 확인하고, 중복된 값이면 건너뛰도록 구현되어 있습니다.

 

2. 투 포인터 풀이

 세 수의 합을 구하기 위해서는 세 개의 변수가 필요합니다.

 한 개의 변수를 고정시켜두고 두 개의 변수는 투 포인터로 간격을 좁혀가면서 합을 계산합니다.

 

def threeSum(nums):
    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:
            summation = nums[i] + nums[left]
            if summation < 0:
                left += 1
            elif summation > 0:
                right -= 1
            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
                left += 1
                right -= 1
    return result