3Sum Closest

3Sum Closest

[문제]
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.

[입력 조건]
3 <= nums.length <= 500
-1000 <= nums[i] <= 1000
-104 <= target <= 104

[내 풀이]

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        closest_sum = float('inf')
        
        for i in range(len(nums) - 2):
            left, right = i + 1, len(nums) - 1
            
            while left < right:
                current_sum = nums[i] + nums[left] + nums[right]
                
                if abs(target - current_sum) < abs(target - closest_sum):
                    closest_sum = current_sum
                
                if current_sum < target:
                    left += 1
                elif current_sum > target:
                    right -= 1
                else:
                    return closest_sum
                
        return closest_sum

처음에는 itertools.combinations를 활용해서 모든 가능한 세 숫자 조합을 찾아보았는데, 입력이 커질수록 효율성이 떨어져서 투 포인터 방식으로 전략을 변경했습니다.

투 포인터 방식을 적용하면서 배열을 먼저 정렬하고, 두 개의 포인터를 이동시켜가며 원하는 조건을 만족하는 값을 찾았습니다. 이렇게 하면 시간 복잡도가 낮아지면서도 원하는 결과를 얻을 수 있었습니다.

투 포인터를 활용하니 더 효율적으로 문제를 해결할 수 있었다는 느낌이 들었습니다. 앞으로도 이런 상황에서 더 나은 접근법을 찾아보고 싶어졌습니다.

[출처]
https://leetcode.com/problems/3sum-closest/description/