[LeetCode]3Sum Closest

문제

 

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

 

my Code

class Solution(object):
    def threeSumClosest(self, nums, target):
        nums.sort()
        ans = sum(nums[:3])
        minDiff = ans - target
        n = len(nums)
       
        for i in range(n-2):
            l , r = i+1, n-1
            small = nums[i] + nums[l] + nums[l+1]
            large = nums[i] + nums[r] + nums[r-1]
            if small > target :
                minDiff = min(minDiff , small - target , key = abs)
            elif large < target :
                minDiff = min(minDiff , large - target , key = abs)
            else :
                while l < r :
                    cur_sum = nums[i] + nums[l] + nums[r]
                    if cur_sum < target : l +=1
                    elif cur_sum > target : r -=1
                    else : return target
                    minDiff = min(minDiff, cur_sum - target, key= abs)
        return target + minDiff

 

접근법

3개의 수를 선택했을때 target보다 작으면 더 큰수를 선택해야하고 그 반대의 경우 작은 수를 선택하기 위해 먼저 sorting을 한다.

왼쪽부터 숫자들을 하나씩 탐색하면서 지금 선택한 첫번째 수를 제외한 나머지(오른쪽의 수)들중에 가장 작은 수와 가장 큰수의 합으로 시작하여 그 세개의 수의 합과 target간의 차이를 줄일 수 있는 방향으로 선택한 오른쪽수 와 왼쪽수를 옮겨서 최소한의 차이를 구해나간다.

 

배운점

1. 최대한 가지치기 할 수 있는 경우들을 가지치기 하는 것이 좋다.

small 과 large를 구하여 기준수(num[i])에서 만들 수 있는 가장 작은수 보다 도 target이 작으면 가장 작은수와의 차이가 가장 작은 차이가 될 것이고 마찬가지로 가장 큰 수보다 target이 크면 가장 큰수와 target의 차이가 가장 작은 차이가 될 것이다. 

2. 최대한 변수를 안쓸 수 있는 방향을 생각해보자 

처음 코드에서는 ans라는 가장 적은 차이가 나는 수를 들고 있을 변수를 만들어서 if문을 사용하여 minDiff가 업데이트 될때마다 ans도 업데이트해주는 코드를 적었었다. 하지만 사실 target과의 차이만 가지고도 target + 차이값 으로 결과값을 구할 수 있다. 

min()함수에 key로 abs를 사용하여 비교할 수 있다는 점을 알게 되고나니, 최소 차이값을 절대값으로 들고있을 이유가 없어지면서 변수를 소거해도 문제가 되지 않았다.