3Sum Closest

문제 링크 : https://leetcode.com/problems/3sum-closest/

3Sum Closest - LeetCode

문제 해설 : n개의 정수로 이루어진 배열 nums가 주어집니다. nums의 요소 중 3개의 합이 target에 가장 가까운 경우를 찾아 그 합을 반환하세요. 각각의 입력에 대해 정확히 하나의 해답만 있다고 가정해도 좋습니다.

 

제한 사항

1) 3 <= nums.length <= 10^3

2) -10^3 <= nums[i] <= 10^3

3) -10^4 <= target <= 10^4

 

 

 

접근 방법

 비슷한 유형의 문제로 배열 안에서 두 수의 합이 target에 가장 가까운 경우를 찾는 문제를 떠올렸습니다.

두 수의 합을 구하는 경우, 주어진 배열 nums의 길이가 1000 이하이므로 모든 요소를 일일히 탐색해도 최대 O(10^6)로 문제를 해결할 수 있습니다.

 이 문제는 세 수의 합을 구하는 문제이므로 두 수의 합을 우선 구한 뒤, target에 가장 가까운 값을 만들기 위한 나머지 요소를 이진 탐색으로 구하려 했습니다.

from typing import List
from bisect import bisect_left

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        answer = sum(nums[:3])

        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                find = target - (nums[i] + nums[j])
                idx = bisect_left(nums, find, lo=j+1)

                if idx - 1 > j:
                    if abs(answer - target) > abs(nums[idx-1] + nums[i] + nums[j] - target):
                        answer = nums[idx-1] + nums[i] + nums[j]

                if idx < len(nums):
                    if abs(answer - target) > abs(nums[idx] + nums[i] + nums[j] - target):
                        answer = nums[idx] + nums[i] + nums[j]
        return answer

 

코드 해설

find는 nums[i]와 nums[j]를 더해 target에 가장 가깝게 되는 값

즉, 배열 안에서 이상적으로 찾고 싶은 값입니다.

 

이진 탐색으로 find에 가까운 값의 인덱스를 구하고 이를 idx에 저장합니다.

 

idx와 그 이전 값에 대하여 nums[i]와 nums[j]를 각각 더하고

target과 차이를 구합니다.

 

 

 

개선점

leetcode 제출 결과 실행 속도가 다른 솔루션들에 비해 상당히 늦은 점을 확인했습니다.

더 나은 방법을 알기 위해 다른 분들의 코드를 참고했습니다.

 

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        
        diff = float('inf')
        nums.sort()
        
        for i in range(len(nums)):
            l,r = i+1, len(nums) - 1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if abs(target - s) < abs(diff):
                    diff = target - s
                    
                if s < target:
                    l += 1
                else:
                    r -= 1
                    
            if diff == 0:
                break
                
        return target - diff

세 수의 합을 저장하지 않고 target과 차이를 저장하는 diff를 사용했습니다.

이진 탐색 대신 투포인터를 사용하였습니다.