📕문제

[LeetCode] 15. 3Sum

문제 설명

숫자 리스트에서 중복 사용 없이 3개의 숫자합이 0이 되는 조합을 찾는 문제다.
예를들어 [-1, 0, 1, 2, -1, -4] 에서 3개의 숫자합이 0인 조합은 [-1, -1, 2], [-1, 0, 1] 2개다.

---

📝풀이

처음 생각한 아이디어는 다음과 같다.

• combinations를 통해 리스트에서 3개의 수 조합을 구한다.
• 중복된 조합은 제거한다.
• 조합들 중 합이 0인 조합을 찾는다.

from itertools import combinations
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        coms = set(tuple(combinations(sorted(nums), 3)))
        result = []
        for com in coms:
            if sum(com) == 0:
                result.append(list(com))
        return result

결과는 시간초과..!

생각해보면 당연한 것 같다. 세 숫자의 조합을 모두 구하는데 있어 $O(n^3)$의 시간복잡도를 가지게 되므로 굉장히 비효율적이다.

---

다음으로 생각한 아이디어는 투포인터다.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = set()
        for left in range(len(nums)-2):
            middle, right = left+1, len(nums)-1
            while middle < right:
                l, m, r = nums[left], nums[middle], nums[right]
                if l + m + r == 0:
                    result.add((l, m, r))
                    middle += 1
                    right -= 1
                elif l + m + r < 0:
                    middle += 1
                else:
                    right -= 1
        return list(result)

• 먼저 리스트를 정렬한다.
• left를 1씩 증가시키며 left+1 ~ len(nums)-1 범위에서 middle, right 투포인터를 이용한다.
  • 숫자합 == 0 : 데이터 저장, middle은 증가 right는 감소
  • 숫자합 < 0 : middle 증가
  • 숫자합 < 0 : right 감소
• result는 set()이기 때문에 중복된 값이 제거된다.

통과는 했지만 실행시간이 아쉽다..

실행시간을 줄일 방법을 생각하던 반복문에서 중복된 수를 스킵하면 실행시간도 줄을뿐더러 조합의 중복을 검사할 필요도 없어진다는 것을 깨닫고 코드를 개선했다. 또, 하다보니 이런저런 수정사항도 늘어났다.

최종 코드

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []
        if nums[0] > 0 or nums[-1] < 0:
            return result
        for start in range(len(nums)-2):
            if nums[start] > 0:
                break
            if start > 0 and nums[start-1] == nums[start]:
                continue
            left, right = start+1, len(nums)-1
            while left < right:
                total = nums[start] + nums[left] + nums[right]
                if total < 0:
                    left += 1
                elif total > 0:
                    right -= 1
                else:
                    result.append([nums[start], nums[left], nums[right]])
                    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 result

• 리스트에서 가장 작은 수가 양수거나 가장 큰 수가 음수면 합이 0이 될 수가 없으므로 빈 리스트를 반환한다.
• nums[start]가 양수면 탐색 중단.(위와 같은 이유)
• start, left, right에 대해 중복을 스킵한다.
• 반복문 순서 변경. 테스트케이스별로 다른 결과를 가지지만 대부분의 경우 합이 0임을 찾은 경우보다 포인터를 이동하며 탐색하는 경우가 많다고 생각해 순서를 변경해보았다.(실제로 실행시간이 줄었다!)

코드의 길이는 많이 늘었지만 그만큼 실행시간도 많이 줄었다.

Runtime을 줄이기 위한 흔적들..