[LeetCode - DiDi Labs 기출 문제] 3Sum Closest

16. 3Sum Closest

 

Medium

Given an integer array nums of length n 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 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Example 2:

Input: nums = [0,0,0], target = 1
Output: 0
Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).

 

Constraints:

• 3 <= nums.length <= 500
• -1000 <= nums[i] <= 1000
• -104 <= target <= 104

---

문제 풀이

• 주어진 숫자 배열에서 세개의 숫자를 선택한 합이 target 과 가장 가까울때, 세개 숫자의 합을 출력한다.
• 문제 제한을 보면 숫자들의 갯수는 최악의 경우 500개이며 이는 n^2 으로도 풀린다. 
• 숫자의 조합을 다 찾아야하는데, 재귀함수를 사용한다면 n! 시간이 걸리고 실제로 500 * 499 * 498 = 1 억 정도 걸릴 것이다. 
• 재귀함수를 사용해서 풀어도 상관없지만, 단순하게 sort 를 사용하여 풀어도 비슷한 속도가 나올 것으로 생각된다.
  • sort 풀이법
    • 숫자 배열을 정렬해준다.
    • 반복문으로 첫 번째 숫자를 선택하고, 그 다음 자리 숫자와 맨뒤 자리 숫자를 선택하여 합을 계산한다.
    • 그 합과 target의 차와 기존 정답으로 정한 값과 target 차를 비교하여 적은 숫자를 정답으로 정한다. 
    • 그리고 만약 숫자 세개를 합친 숫자가 target 보다 작다면, 두번째 숫자자리를 늘려 탐색한다.
    • target 보다 크다면 마지막 더할 숫자 위치를 감소 시켜 탐색한다. 
    • 즉, 두번째 세번째 위치가 될 숫자를 세개 숫자 합과 target의 크기비교를 해서 선택해야한다.
    • 그러기 위해서 숫자를 정렬해주었다. 

소스 코드

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        num_len = len(nums)
        answer = 10e9
        total = 0
        if num_len == 3:
            return sum(nums)
        nums.sort()
        for idx in range(num_len):
            first = nums[idx]
            l, r = idx + 1, num_len - 1
            while l < r:
                total = first + nums[l] + nums[r]
                if total == target:
                    return target
                if abs(total - target) < abs(answer - target):
                    answer = total
                if total < target:
                    l += 1
                else:
                    r -= 1
        return answer