[Leetcode] 18. 4Sum_해설, 풀이, 설명

---

안녕하세요, HELLO

 

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

 

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

---

STEP 1. '4Sum' 알고리즘 문제

 

STEP 2. '4Sum' 코드(code)

 

STEP 3. '4Sum' 해설

 

STEP 4. '4Sum' solution

 

반응형

 

STEP 1. '4Sum' 알고리즘 문제

 

 

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that, and you may return the answer in any order.

 

정수 배열 수가 주어지면 다음과 같은 고유한 사중수 [nums[a], nums[b], nums[c], nums[d]의 배열을 반환합니다. 그리고 순서에 상관없이 정답을 출력하면 됩니다.

 

• 0 <= a, b, c, d < n
• a, b, c, and d are distinct.
• nums[a] + nums[b] + nums[c] + nums[d] == target

Constraints:

• 1 <= nums.length <= 200
• -109 <= nums[i] <= 109
• -109 <= target <= 109

---

STEP 2. '4Sum' 코드(code)

 

■ Runtime: 1565 ms, faster than 35.80% of Python3 online submissions for 4Sum.
■ Memory Usage: 14 MB, less than 64.01% of Python3 online submissions for 4Sum.

 

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        res = set()

        for i in range(len(nums)-3):
            for j in range(i+1, len(nums) -2):
                
                l, r = j+1, len(nums) -1
                check = target - nums[i] - nums[j]
                
                while l < r:
                    if nums[l] + nums[r] == check:
                        res.add((nums[i], nums[j], nums[l], nums[r]))
                    
                    if nums[l] + nums[r] > check:
                        r -= 1
                    else: #nums[l] + nums[r] < check:
                        l += 1
        
        return res

---

STEP 3. '4Sum' 해설

 

2sum, 3sum 문제와 동일하게 2개의 pointer (left, right)를 활용해서 계산했습니다. 3sum은 변수가 3개이기에, target에서 하나의 변수를 빼서 2개의 pointer로 답을 찾을 수 있지만, 4sum은 변수가 4개이기에, 2중 반복문을 통해서 계산했습니다. 이로 인해 속도가 저하되는 문제가 있었습니다.

 

아래 solution은 다른 방법을 통해 문제를 접근하였으며, 참고하시기 바랍니다.

 

 

STEP 4. '4Sum' solution

 

추가적으로, Leetcode에서 제공해준 solution 코드를 살펴보겠습니다.

 

■ Runtime: 859 ms, faster than 69.78% of Python3 online submissions for 4Sum.
■ Memory Usage: 859 ms, faster than 69.78% of Python3 online submissions for 4Sum.

 

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        res, quad = [], []
        
        def ksum(k, start, target):
            if k != 2:
                for i in range(start, len(nums) -k+1):
                    if i > start and nums[i] == nums[i-1]:
                        continue
                    
                    quad.append(nums[i])
                    ksum(k-1, i+1, target - nums[i])
                    quad.pop()
                
                return
        
            l, r = start, len(nums) -1
            
            while l < r:
                if nums[l] + nums[r] < target:
                    l += 1
                elif nums[l] + nums[r] > target:
                    r -= 1
                else:
                    res.append(quad + [nums[l], nums[r]])
                    l += 1
                    while l < r and nums[l] == nums[l-1]:
                        l += 1
                        
        ksum(4, 0, target)
        return res

---

■ 마무리

 

오늘은 Leetcode 알고리즘 문제 '18. 4sum'에 대해서 알아봤습니다.

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

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

감사합니다.