09. 3Sum

🎯 leetcode - 15. 3Sum

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 9번 문제
- 3개의 합이 0이 되는 서로 다른 숫자쌍을 모두 구하시오

📌 날짜

2020.01.22

📌 시도 횟수

2 try

💡 (시간 초과) 코드

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        num_dict = {}
        num_list = []
        for idx, num in enumerate(nums):
            num_dict[num] = idx

        for i in range(len(nums) - 1):
            for j in range(i + 1, len(nums)):
                key = -(nums[i] + nums[j])
                if key in num_dict and num_dict[key] != i and num_dict[key] != j:
                    li = sorted([nums[i], nums[j], key])
                    if li not in num_list:
                        num_list.append(li)
        return num_list

💡 문제 해결 방법

- 일단 2중 for문을 통해 2개의 원소에 접근한다.
- 그리고 (첫번째 수 + 두번째 수 + 세번째 수 = 0)이 되는 세번째 수가 존재하는지 찾는다.
- -(첫번째 수 + 두번째 수)가 dict의 key에 들어있는 지 검사했다.
- 만약 세번째 수가 첫/두번째 수가 아니면서 dict에 들어있으면 해당 숫자쌍을 추가한다.
- 단, 조합의 순서는 고려하지 않으므로 sorted와 set의 특성을 이용하여 중복된 쌍을 1개로 처리했다.

💡 새롭게 알게 된 점

- 

❌ (한번에 맞추지 못한 경우) 오답의 원인

>> 실행은 된다ㅠㅠ
- 시간 초과가 발생해서 통과하지 못했다.
- 이렇게 O(n^3)으로 풀게되면 시간 초과가 발생하게 된다.
- 브루트 포스(3중 for문)으로 안 풀어보려고 조금 다르게 풀긴 했는데
솔직히 내가 봐도 좋은 풀이 같아보이진 않는다ㅋㅋ😥😥😥
사실 이 방법도 그냥 브루트 포스 방법에서 아주 살짝 바꾼 거여서ㅠㅠ

---

😉 다른 풀이

📌 하나. 브루트 포스 (⚠시간 초과 발생!有)

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

        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            for j in range(i + 1, len(nums) - 1):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                for k in range(j + 1, len(nums)):
                    if k > j + 1 and nums[k] == nums[k - 1]:
                        continue
                    if nums[i] + nums[j] + nums[k] == 0:
                        result.append([nums[i], nums[j], nums[k]])
        return result

💡 새롭게 알게 된 점

- 위의 방법이 브루트 포스로 푼 방법이다.
- 이 코드는 시간 복잡도가 O(n^3)이다.
- 틀린 부분은 없지만 시간초과가 발생하여 리트코드 내에서 통과가 안되는 방법이다!!
- 따라서 O(n^2)로 최적화 시킬 수 있는 방법을 찾아야 한다.

---

📌 둘. 투 포인터로 합 계산하기

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

        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            left, right = i + 1, len(nums) - 1
            while left < right:
                sum = nums[i] + nums[left] + nums[right]
                if sum < 0:
                    left += 1
                elif sum > 0:
                    right -= 1
                else:
                    result.append([nums[i], 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

💡 새롭게 알게 된 점

- 투 포인터 기법을 사용하면 동시에 2가지 원소에 접근 가능하므로
for문을 절약하여 사용할 수 있음을 알게 되었다.
- 위의 코드의 경우 기존 코드의 O(n^3)을 O(n^2)로 절약할 수 있게 해주었다.

👀 투 포인터

• 대개 시작점과 끝점(왼쪽 포인터와 오른쪽 포인터) 두 지점을 기준으로 하는 문제 풀이 전략
• 보통은 이미 정렬된 배열을 대상으로 한다.
• 2개의 포인터가 자유롭게 움직이며 문제를 풀이한다.