[Leetcode] 16. 3Sum Closest_해설, 풀이, 설명

---

안녕하세요, HELLO

 

오늘은 Leetcode 알고리즘 문제 '16. 3Sum Closest'에 대해서 살펴보고자 합니다. 

 

알고리즘 문제, 코드, 해설 그리고 Leetcode에서 제공해준 solution 순서대로 정리하였습니다.

---

STEP 1. '3Sum Closest' 알고리즘 문제

 

STEP 2. '3Sum Closest' 코드(code)

 

STEP 3. '3Sum Closest' 해설

 

반응형

 

STEP 1. '3Sum Closest' 알고리즘 문제

 

16번 문제는 15번 문제 3SUM과 유사한 문제입니다.

 

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.

 

길이가 n인 정수 배열 숫자와 목표값이 주어지면 합이 목푯값에 가장 가깝도록 세 개의 정수를 숫자로 구합니다. 세 정수의 합을 반환합니다. 문제는 정확히 하나의 정답만 있다고 가정합니다.

 

Constraints:

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

---

STEP 2. '3Sum Closest' 코드(code)

 

■ Runtime: 425 ms, faster than 37.83% of Python3 online submissions for 3Sum Closest.
■ Memory Usage: 13.8 MB, less than 96.89% of Python3 online submissions for 3Sum Closest.

 

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        best_s = 100000 # initialize the 3 sum number
        
        nums.sort()
        
        for i in range(0, len(nums)-2):
            
            if nums[i] == nums[i-1] and i > 0:
                continue
                
            lower = i + 1
            upper = len(nums) - 1
            
            while lower < upper:
                s = nums[i] + nums[lower] + nums[upper]
                
                if s == target:
                    return s
                
                if abs(target - s) < abs(target - best_s):
                    best_s = s
                    
                if s <= target:
                    lower += 1
                    
                    while nums[lower] == nums[lower - 1] and lower < upper:
                        lower += 1
                
                else:
                    upper -= 1
                
        return best_s

---

STEP 3. '3Sum Closest' 해설

 

전체적으로 코드는 3sum과 동일하게, dynamic programming을 통해 3개 정수의 합을 비교합니다. 다만, 추가적으로 target이 없는 경우에는 가장 인접한 값을 구하게 됩니다.

 

이번 문제를 풀면서 살펴본 영상 URL입니다. 

 

 

■ 마무리

 

오늘은 Leetcode 알고리즘 문제 '16. 3Sum Closest'에 대해서 알아봤습니다.

좋아요와 댓글 부탁드리며,

오늘 하루도 즐거운 날 되시길 기도하겠습니다 :)

감사합니다.