[LeetCode] 15. 3Sum (세 수의 합)

yunan·2021년 1월 18일

leetcode 파이썬알고리즘인터뷰

🐬 알고리즘 풀이 🐬

목록 보기

43/74

🔦 문제 링크

🔊 파이썬 알고리즘 인터뷰 책을 참고했습니다.

문제

배열을 입력받아 합으로 0을 만들 수 있는 요소 값들을 리스트에 넣어서 반환하라. 중복값은 제외시켜야만 한다.

✍️ 풀이

못품..타임아웃

타임아웃 풀이
- for문을 3개를 돌려 O(n^3)으로 해결했더니 역시나 시간 초과가 발생하였다.
투 포인터를 이용한 O(n^2) 최적화

첫번째 숫자를 정해두고 나머지 두개는 투 포인터를 이용해서 구하면 O(n^2)만에 답을 구할수 있다.

투포인터 사용을 위해 소팅할 것
첫번째 숫자를 결정한 후 나머지 숫자는 투 포인터를 통해 결정해나갈 것
구한 값이 이미 있는 값이면 중복이므로 반환 값에 넣지 않는다.
sum == 0 일때 left, right 둘 다 이동한다.(하나만 움직여선 0이 될수 없다.)

🛠 코드

리스트를 원소를 앞-뒤로 검사하는 가장 기본적인 풀이방법이다.

투 포인터 풀이

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ret = []
        nums.sort()
        for i in range(len(nums)):
            left, right = i + 1, len(nums) - 1
            while left < right:
                sm = nums[i] + nums[left] + nums[right]
                if sm < 0:
                    left += 1
                elif sm > 0:
                    right -= 1
                else:
                    temp = [nums[i], nums[left], nums[right]]
                    if temp not in ret:
                        ret.append(temp)
                    left += 1
                    right -= 1
        return ret

투 포인터 풀이에서 중복 검사를 개선한 코드

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ret = []
        nums.sort()
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            left, right = i + 1, len(nums) - 1
            while left < right:
                sm = nums[i] + nums[left] + nums[right]
                if sm < 0:
                    left += 1
                elif sm > 0:
                    right -= 1
                else:
                    temp = [nums[i], nums[left], nums[right]]
                    ret.append(temp)
                    # 중복 검사를 따로 진행해서 쓸데없는 연산을 없앨 수 있다.
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                        
                    left += 1
                    right -= 1
        return ret