LeetCode 15. 3Sum

파이썬 알고리즘 인터뷰 문제 9번(리트코드 15번) 3Sum
https://leetcode.com/problems/3sum/

나의 풀이

#Two Sum 문제 방법을 이용했는데 너무 느리다. 

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()  # 배열을 오름차순으로 정렬
        result = set()  # 결과를 저장할 집합 (중복 제거)

        for left in range(len(nums) - 2):  # left 포인터: 첫 번째 숫자를 고정
            # 특정 숫자가 너무 많이 반복되면 건너뛰기
            if left + 4 < len(nums) - 2 and nums[left] == nums[left + 4]:
                continue
            
            complement = dict()  # 보완 값을 저장할 딕셔너리
            for mid in range(left + 1, len(nums)):  # mid 포인터: 두 번째 숫자를 고정
                if -nums[mid] in complement:  # 세 번째 숫자 확인
                    # 세 숫자의 합이 0이 되는 경우를 결과에 추가
                    result.add((complement[-nums[mid]][0], complement[-nums[mid]][1], nums[mid]))
                else:
                    # 현재 숫자 쌍 (nums[left], nums[mid])을 딕셔너리에 추가
                    complement[nums[left] + nums[mid]] = [nums[left], nums[mid]]
        
        # 결과를 리스트로 변환하여 반환
        return [list(x) for x in result]

다른 풀이(Two Pointers)

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()  # 배열을 오름차순으로 정렬
        result = []  # 결과를 저장할 리스트

        for left in range(len(nums) - 2):  # 첫 번째 포인터 (left)를 설정
            # 이전 숫자와 동일하면 중복이므로 건너뛰기
            if left > 0 and nums[left] == nums[left - 1]:
                continue
            
            target = -nums[left]  # 두 번째와 세 번째 숫자의 합이 이 값이 되어야 함
            mid, right = left + 1, len(nums) - 1  # 두 번째와 세 번째 포인터 초기화
            
            while mid < right:  # 두 번째 포인터(mid)와 세 번째 포인터(right) 간 탐색
                curr = nums[mid] + nums[right]  # 현재 두 숫자의 합 계산
                if target == curr:  # 세 숫자의 합이 0인 경우
                    result.append([nums[left], nums[mid], nums[right]])  # 결과에 추가
                    mid += 1  # 두 번째 포인터를 오른쪽으로 이동
                    right -= 1  # 세 번째 포인터를 왼쪽으로 이동

                    # 중복된 숫자를 건너뛰기
                    while mid <= right and nums[mid] == nums[mid - 1]:
                        mid += 1
                    while mid <= right and nums[right] == nums[right + 1]:
                        right -= 1
                elif target < curr:  # 현재 합이 목표보다 크면 세 번째 포인터 이동
                    right -= 1
                else:  # 현재 합이 목표보다 작으면 두 번째 포인터 이동
                    mid += 1
        
        return result  # 결과 반환

배운 점

• 정답인 경우를 찾았을 때는 mid, right를 동시에 옮길 수 있다는 것이 포인트
• mid, right 포인터도 옮기고 나서 중복 숫자 건너뛰는 것 빠트리지 않기
• 두 풀이 모두 O(n²)이지만 내 풀이가 많이 느리다.
  • 내 풀이는 Two Sum 문제 풀이법을 적용한 풀이다.
  • 하지만, .sort()가 O(nlogn)이므로 어차피 정렬을 하는게 유리하고,
  • 정렬을 했다면 Two Pointers를 사용하는 것이 자연스럽고 불필요한 연산들이 줄어든다.
  • Two Sum과 달리 딕셔너리를 루프마다 초기화하기 때문에 비효율적이다.