LeetCode [15]: 3Sum

📌 LeetCode [15]: 3Sum

🔗 문제 링크

---

문제 설명 📄

정수 배열 nums가 주어졌을 때, 세 수의 합이 0이 되는 모든 고유한 조합을 반환하는 문제입니다.

• 각 조합은 중복되지 않아야 하며, 순서는 상관없습니다.
• 출력은 리스트의 형태로 반환해야 합니다.

---

문제 접근 방식 📋

1. 정렬된 배열 활용:
   • 배열을 정렬하여 중복 조합을 제거하기 쉽고, 탐색 범위를 줄일 수 있습니다.
2. 투 포인터 사용:
   • 첫 번째 숫자를 고정한 후, 나머지 두 수를 투 포인터로 찾습니다.
   • 투 포인터를 활용하면 두 수의 합을 효율적으로 계산할 수 있습니다.
3. 중복 제거:
   • 동일한 숫자가 연속으로 나오는 경우 건너뛰어 중복된 조합을 제거합니다.
   • 결과는 set을 사용해 중복 방지.

---

Solution 💻

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        answer = set()

        for i in range(len(nums) - 2):
            target = -nums[i]
            left, right = i + 1, len(nums) - 1

            while left < right:
                value = nums[left] + nums[right]
                if value == target:
                    answer.add(tuple(sorted([nums[i], nums[left], nums[right]])))
                    left += 1
                    right -= 1
                elif value < target:
                    left += 1
                else:
                    right -= 1

        return [list(i) for i in answer]

시간 복잡도 분석 ⏲️

• 정렬: (O(n \log n))
  • 한 번만 정렬.
• 투 포인터 탐색: (O(n^2))
  • 첫 번째 루프에서 (O(n)), 내부 투 포인터 탐색에서 (O(n)).
• 총 시간 복잡도: (O(n^2))

공간 복잡도 분석 🗄️

• 결과 저장: (O(k)), (k)는 결과 조합의 개수.
• 총 공간 복잡도: (O(n + k)) (정렬된 배열 저장 및 결과 저장 공간).

---

리팩토링 🛠️

개선된 코드

중복된 조합을 제거하기 위해 set 대신, 정렬된 배열에서 중복 값을 건너뛰는 방식으로 처리합니다.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        answer = []

        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i - 1]:  # 중복된 값 건너뛰기
                continue

            target = -nums[i]
            left, right = i + 1, len(nums) - 1

            while left < right:
                value = nums[left] + nums[right]
                if value == target:
                    answer.append([nums[i], nums[left], nums[right]])
                    left += 1
                    right -= 1

                    # 중복된 값 건너뛰기
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1

                elif value < target:
                    left += 1
                else:
                    right -= 1

        return answer

리팩토링 코드의 장점

1. set 제거:
   • 중복된 결과를 방지하기 위해 정렬된 배열의 특성을 활용하여 중복 제거.
2. 메모리 효율성:
   • set을 사용하지 않아 메모리 사용량 감소.
3. 간결함:
   • 결과 추가 시 정렬이 필요하지 않으므로 코드가 더 간단해집니다.

시간 복잡도 ⏲️

• 정렬 및 투 포인터 탐색은 기존 코드와 동일한 (O(n^2))입니다.

---