LeetCode 16(3Sum Closest, Python)

1. 문제 링크

• https://leetcode.com/problems/3sum-closest/

LeetCode - The World's Leading Online Programming Learning Platform

2. 문제 설명

• 리스트 nums와 target 수가 주어졌을 때 nums에서 서로 다른 세 개를 더하여 만들 수 있는 값 중 target과 가장 가까운 값을 반환
• 예시) nums = [-1,2,1,-4], target = 1일 때, -1 + 2 +1 = 2가 target과 가장 가까우므로 2를 반환 

3. 처음 풀이

• 직전에 풀었던 3Sum과 비슷한 방식으로 two pointer, sorting을 이용 
• nums를 우선 오름차순으로 sorting 한 후, 
• start_index를 for문을 돌리는데,
  • 바로 이후 index를 left라 정의, 
  • 가장 마지막 index를 end_index라 정의한 후, 특정 규칙에 따라 left, end_index를 이동시키고, left < end_index가 아닐 때 while문을 멈추게 하였음.
• 특정 규칙은? 
  • 우선 초기 gap을 큰 숫자로 셋팅하고 (문제의 contraints 상, gap은 13000보다 클 수 없으므로, 13001로 셋팅)
  • 현재의 gap (cur_gap)을 계산한 후, (cur_gap = nums[start_index] + nums[left] + nums[end_index] - target
    • 만약, cur_gap 의 절댓값이 gap보다 작으면, gap을 cur_gap으로 업데이트를 해주고 
  • 만약 cur_gap 이 양수면? 
    • end_index가 작아지는 방향(그래야 총 합이 줄어드므로)으로 이동
  • 만약 cur_gap 이 음수면?
    • left가 커지는 방향(그래야 총 합이 커지고, gap이 줄어들 수 있으므로)으로 이동 
• 최종적으로 gap+target을 반환하는 구조로 코드 작성 

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:

        nums.sort()
        gap = 13001

        for start_index in range(len(nums)-2): 

            end_index = len(nums) -1 
            left = start_index+1

            while left < end_index:
                if gap == 0:
                    return target

                cur_gap = nums[start_index] +nums[left] + nums[end_index] - target

                if abs(cur_gap) < abs(gap):
                    gap = cur_gap

                if cur_gap > 0:
                    end_index -=1

                else:
                    left +=1
                
        return gap+target

• runtime beats는 54% 정도로, 막 높은 편은 아니었음

4. 다른 풀이

• beats 98% 풀이 → recursive, 재귀함수 이용 

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        # 리스트를 정렬하여 이후 이진 탐색과 유사한 방식으로 탐색하기 위해 정렬
        nums.sort()
        # kSumClosest 함수 호출하여 결과 반환
        return self.kSumClosest(nums, 3, target)
        
    def kSumClosest(self, nums, k, target):
        N = len(nums)
        
        # 리스트에 k개의 요소만 있는 특수한 경우. 해당 요소들의 합 반환
        if N == k:
            return sum(nums[:k])
        
        # target이 너무 작은 특수 케이스, 가장 작은 합보다 작음
        if sum(nums[:k]) >= target:
            return sum(nums[:k])
        
        # target이 너무 큰 특수 케이스, 가장 큰 합보다 큼
        if sum(nums[-k:]) <= target:
            return sum(nums[-k:])
        
        # k가 1인 경우, 가장 가까운 요소 반환(재귀함수 base case)
        if k == 1:
            # 요소와 목표값과의 차이 계산
            deltas = [(x, abs(target-x)) for x in nums]
            # 차이가 가장 작은 요소 반환
            return min(deltas, key=lambda x: x[1])[0]
        
        # 한 요소를 선택하고, k-1에 대해 재귀적으로 가장 가까운 매치를 검색
        closest = sum(nums[:k])
        for i, x in enumerate(nums[:-k+1]):
            # 중복된 x값 처리를 위한 부분 최적화
            if i > 0 and nums[i-1] == x:
                continue
            
            # 현재 x값을 제외하고, 재귀적으로 가장 가까운 매치 검색
            bestMatch = self.kSumClosest(nums[i+1:], k-1, target-x)
            current = x + bestMatch
            
            # 현재 합이 가장 가까우면 closest 갱신
            if abs(target-current) < abs(target-closest):
                if target == current:
                    return current
                else:
                    closest = current
        
        return closest

5. 배운 점 

• two pointer 쓰는 게 약간 생소했었는데, 3Sum, SSumClosest 거치면서 약간 익숙해졌음.
• for 문을 한 개씩 줄여나가는 방법 고민!