[Leetcode] 15. 3Sum_해설, 풀이, 설명

---

안녕하세요, HELLO

 

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

 

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

---

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

 

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

 

STEP 3. '3Sum' 해설

 

STEP 4. '3Sum' solution

 

반응형

 

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

 

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]]

such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

 

정수 배열 번호가 주어지면 모든 삼중항 [nums[i], nums[j], nums[k]]을 반환합니다.
i != j, i != k, j != k, nums[i] + nums[j] + nums[k] == 0이 되어야 합니다.

Notice that the solution set must not contain duplicate triplets.

정답에는 중복된 조합이 없어야 합니다.

(예를 들어, [0,0,0], [0,0,0]이 계산되었다면, 정답에는 [0,0,0] 하나만 있어야 합니다.)

 

Constraints:

• 0 <= nums.length <= 3000
• -105 <= nums[i] <= 105

---

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

 

Time Limit Exceeded로 코드를 다 작성하였지만, 목표한 time 내에는 작동하지 않았습니다.

 

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        import numpy as np
        
        # nums has less than 3 digits
        if len(nums) < 3:
            lst = []

        # not the first case
        else:
            nums = sorted(nums)
            lst = []
            i = 0
            j = 1
            
            while j < len(nums) -1 :
                while nums[i] + nums[j] <= 0:
                    c =  (nums[i] + nums[j]) * -1
                    if c in nums[j+1:]:
                        lst.append([nums[i], nums[j], c])

                    # iterate until the nums
                    if j != len(nums) - 1:
                        j += 1
                    else:
                        break

                i += 1
                j = i + 1

            lst = np.unique(lst, axis=0).tolist()

        return lst

---

STEP 3. '3Sum' 해설

 

문제 접근방식은 3개의 합이 0이 되어야 하기에, sorted array를 통해 연산을 효율적으로 진행했습니다. 왜냐하면 3개의 합이 0이 되려면 적어도 1개는 음수이어야 하기 때문입니다. (예외 0, 0, 0) 그래서 3개의 합이 양수가 되는 시점에는 더 이상 연산을 할 필요가 없습니다. 첫 번째 값을 설정하고, 이후 나머지 2개의 합은 two sum 문제와 동일하게 Left, right의 비교로 계산합니다. 

 

2022.03.28 - [DATA_SCIENCE/LeetCode] - [Leetcode] 1. Two sum_해설, 풀이, 설명

 

 

STEP 4. '3Sum' solution

 

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

 

■ Runtime: 752 ms, faster than 89.70% of Python3 online submissions for 3Sum.
■ Memory Usage: 18.2 MB, less than 44.29% of Python3 online submissions for 3Sum.

 

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        
        if len(nums) < 3:
            return res
        
        else: 
            nums.sort()
            
            for i, a in enumerate(nums):
                if i > 0 and a == nums[i - 1]:
                    continue
                    
                # left and right
                l, r = i + 1, len(nums) - 1
                
                while l < r:
                    threeSum = a + nums[l] + nums[r]
                    
                    if threeSum > 0:
                        r -= 1
                    elif threeSum < 0:
                        l += 1
                    else: # threeSum == 0:
                        res.append([a, nums[l], nums[r]])
                        l += 1
                        while nums[l] == nums[l-1] and l < r:
                            l += 1
                        
            return res

---

■ 마무리

 

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

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

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

감사합니다.