[LeetCode - 3Sum Closest] Python / 파이썬

LeetCode - 3Sum Closest
요즘 '파이썬 알고리즘 인터뷰'라는 책을 공부중에 있다.
책에서 공부한 예제를 제외한 다른문제를 leetcode에서 풀어보는 중이다.

Solution

3Sum 의 응용문제로 입력받은 list의 값들 중
세 수를 골라 더하여 target에 최대한 가까운 세 수의 합을 구하는 문제이다.
투포인터 알고리즘을 이용하면 현재 index, left, right 이렇게 3개의 값에 접근할 수 있다.
먼저 값을 비교하여 포인터를 이동시키기 위해서는 list를 오름차순으로 정렬시킬 필요가 있으며
이렇게 정렬된 list에서 세 값의 합이 target보다 작으면 left가 +1, target보다 크면
right가 -1 씩 포인터가 이동하는 방식으로 target과의 차이가 제일 작은 세 수의 합을 구한다.

Code

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        result = sys.maxsize
        nums.sort()
        
        for i in range(len(nums) - 2):
            left, right = i + 1, len(nums) - 1
            
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            while left < right:
                tmp = nums[i] + nums[left] + nums[right]
                
                if abs(target - tmp) < abs(target - result):
                    result = tmp
                
                if tmp == target:
                    return target
                elif tmp < target:
                    left += 1
                elif tmp > target:
                    right -= 1
        
        return result