Leetcode 15. 3Sum - Python

Leetcode 15 문제 보기

 

문제 이해하기

정수가 담긴 리스트 nums가 있다. (-10^5 <= 정수 num <= 10^5)

이때 리스트의 세 원소를 더해 0이 될 경우, 해당 세 원소의 조합을 출력하라.

결과 set에는 중복된 원소가 존재해서는 안된다.

 

아이디어 구상

본 문제는 LeetCode 1번 문제의 응용 버전이다.

Leetcode 1 문제 보러 가기

 

Leetcode 1 Two Sum 문제와는 다르게, 결과값으로 원소의 index가 아닌 값 그 자체를 출력해야한다.

때문에 본 문제에서는 nums를 정렬한 후 포인터를 사용할 경우, 효율적으로 풀이가 가능하다.

 

세 원소를 더해야하므로 three pointer를 사용해야겠다.

좀 더 깔끔한 구현을 위해 하나의 포인터는 for문을 통해 순차적으로 돌리고,

다른 두 개의 포인터를 조정하며 합이 0이 되는지 검사하면 정답을 얻을 수 있을 것이다.

 

By Mesotes

 

중요한 점은 최종 결과 set에 중복이 있어서는 안된다는 점이다.

이 부분을 어떻게 해결해야할까?

 

두 가지 방법이 떠오른다.

첫째로 가능한 조합을 리스트가 아닌 튜플로 받고 최종 결과를 set으로 하여 중복을 제거하는 방법이다.

파이썬의 set은 리스트를 비롯해 mutable한 값은 원소로 지닐 수 없다.

그러나 tuple처럼 immutable한 값은 원소로 포함가능하다.

 

둘째로 가능한 방법은 포인터 조작 시 중복된 값의 원소를 건너뛰는 것이다.

for문과 투 포인터를 조작하면서 이전 원소의 값과 현재 원소의 값이 동일하다면,

다음 위치로 이동하도록 for문의 index 혹인 포인터를 skip시키면 될 것이다.

 

여기서는 두 번째 방법으로 해결해보겠다.

 

이 때의 시간복잡도는 어떻게 될까?

for문으로 nums를 탐색하면서 투 포인터를 조작해야한다.

때문에 n = len(nums)라 할 경우, Time Complexity ~ O(n ^ 2)일 것이다.

 

풀이

결과를 담을 리스트 res를 선언한다.

res = []

 

만약 len(nums) < 3이라면, 연산을 더 진행할 필요 없이 바로 return해주면 된다. 그렇지 않을 경우, nums를 정렬한다.

if len(nums) < 3:
    return
        
nums.sort()

 

for문을 돌리며 투 포인터를 조작한다.

이 때, for문을 돌릴 시 만약 현재 원소가 이전 원소와 값이 같다면 skip해준다.

마찬가지로 투 포인터 조작 시 동일한 작업을 진행한다.

for i, num in enumerate(nums):
    if i > 0 and num == nums[i - 1]:
        continue
            
    left, right = i + 1, len(nums) - 1
    while left < right:
        three_sum = num + nums[left] + nums[right]
        if three_sum > 0:
            right -= 1
        elif three_sum < 0:
            left += 1
        else:
            res.append([num, nums[left], nums[right]])
            left += 1
            while nums[left] == nums[left - 1] and left < right:
                left += 1

 

전체 코드는 다음과 같다.

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

 

---

Leetcode 15. 3Sum

https://leetcode.com/problems/3sum/​

​

 

 

 

-문제해결흐름을 간단히 정리한 주관적 포스팅-

 

-부족한 설명이 있다면 부디 조언 부탁드립니다-

 

 

 

 

이 포스팅은 쿠팡 파트너스 활동의 일환으로,

이에 따른 일정액의 수수료를 제공받습니다