[LeetCode/Python] 15. 3Sum

ㅎㅎ·2024년 3월 20일

leetcode python

LeetCode

목록 보기

20/33

15. 3Sum

3개의 수의 합이 0이 되는 부분 집합을 찾는 문제다.

Solution

며칠동안 고민했지만 풀리지 않아서 Leetcode에서 제공하는 솔루션 코드를 살펴보았다.

투 포인터 를 사용했다. (left, right)
1. 우선 배열을 정렬한다. 3개 수의 합이 0이 되려면 [0, 0, 0] 인 경우를 제외하고는 최소 하나의 수가 음수여야하기 때문에 오름차순으로 배열을 정렬해 투 포인터를 사용한다.
2. 이전의 수(nums[i-1])와 같은 수라면 중복된 값이므로 continue를 실행해 넘어간다.
3. i번째 수 이후의 수들 중 양 끝의 수를 각각 left, right로 지정해 투 포인터 연산을 수행한다.
4. 세 수의 합계를 구하고 양수면 right를 이동하고 음수면 left를 이동한다.
5. 합계가 0이라면 정답 배열에 추가한 후 left를 중복된 값이 아닐 때까지 이동시킨다.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        if len(nums) < 3: return res
        else: 
            nums.sort() # O(nlogn)
            for i, num in enumerate(nums):
                if i > 0 and num == nums[i - 1]: continue # 중복된 값 넘어가기
                left, right = i + 1, len(nums) - 1 # 왼 오 인덱스를 양 끝(i번째 이후 수들 중)으로 저장
                while left < right:
                    sum3 = num + nums[left] + nums[right] # 세 수의 합계
                    if sum3 > 0: right -= 1 # 양수면 right를 당기기
                    elif sum3 < 0: left += 1 # 양수면 left를 당기기
                    else: # 합계가 0일 때,
                        res.append([num, nums[left], nums[right]]) # 정답 배열에 수 저장
                        left += 1 # left를 당기기
                        while nums[left] == nums[left-1] and left < right: left += 1 # 중복된 값 넘어가기
                        
            return res