[LeetCode]3Sum

https://leetcode.com/problems/3sum/

3Sum - LeetCode

 

문제 분석

합이 0이되는 3개의 숫자를 구하는 문제입니다. 중복된 숫자의 사용이 있다면 제외합니다.

 

처음 시도한 답안 (오답)

import itertools


class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        combinations_ = itertools.combinations(nums, 3)

        answers = []
        for nums in list(combinations_):
            if sum(nums) == 0 and sorted(list(nums)) not in answers:
                answers.append(sorted(list(nums)))

        return answers

접근 방법

1. itertools를 활용해 3글자로 조합을 만듭니다.
2. 조합을 순회하면서 합이 0이 되는 3개의 숫자를 중복되지 않게 넣습니다.

이 답안의 경우 시간초과로 실패하게 됩니다. 파이썬에서 제공되는 조합을 통해 3개로 이루어지는 조합을 만들고 반복하려 했으나 nums의 길이가 길기 때문인지 오답이 되었습니다. 따라서 다른 솔루션을 찾아보았습니다.

 

두번째로 시도한 답안

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

        for idx in range(len(nums)):
            # We need a unique combination of nubmers, so come up with the same fixed number, skip it.
            if idx > 0 and nums[idx] == nums[idx-1]:
                continue

            left = idx + 1
            right = len(nums) - 1
            while left < right:
                if nums[idx] + nums[left] + nums[right] < 0:
                    left += 1
                elif nums[idx] + nums[left] + nums[right] > 0:
                    right -=1
                # 3 Sum is 0.
                else:
                    answer.append([nums[idx], nums[left], nums[right]])
                    left += 1
                    # We need a unique combination of nubmers, so come up with the same left number, skip it.
                    while left < right and nums[left] == nums[left-1]:
                        left += 1
        
        return answer

접근 방법

1. nums 리스트를 크기 오름차순대로 정렬합니다.
2. nums 리스트의 길이만큼 순회합니다.
3. 만약 바로 전에 등장한 숫자와 지금의 숫자가 동일하다면 유니크한 조합을 위해 건너뜁니다.
4. 하나의 고정된 숫자와, left, right 커서를 활용해 내부 반복을 진행합니다.
5. left 와 rigth가 마주할 때까지 반복합니다.
6. 고정된 숫자 + left 커서의 숫자 + right 커서의 숫자의 합이 0보다 작다면, left를 (더 큰수가 있는)오른쪽으로 한 칸 움직입니다.
7. 고정된 숫자 + left 커서의 숫자 + right 커서의 숫자의 합이 0보다 크다면, right를 (더 작은수가 있는)오른쪽으로 한 칸 움직입니다.
8. 고정된 숫자 + left 커서의 숫자 + right 커서의 숫자의 합이 0이라면, 해당 숫자의 조합을 answer에 넣습니다. 
   left 커서를 한칸 오른쪽으로 옮깁니다. 그 후에 동일한 숫자가 사용되는 것을 막고자 left를 숫자가 다를때까지, 오른쪽으로 계속 옮깁니다.

문제의 힌트로서 나온 것처럼 3개의 숫자중 1개의 고정된 숫자와, 2개의 포인터를 활용해 나머지 2개의 숫자를 구하는 방식입니다. 

또한, 중복된 조합을 피하기 위해 반복하는 도중 동일한 숫자가 나오면 넘어간다는 특징이 있습니다. (정렬된 리스트이기에 가능합니다)

 

세번째로 시도한 답안

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

        for idx in range(len(nums)):
            left = idx + 1
            right = len(nums) - 1

            while left < right:
                if nums[idx] + nums[left] + nums[right] < 0:
                    left += 1
                elif nums[idx] + nums[left] + nums[right] > 0:
                    right -= 1
                # 3 Sum is 0.
                else:
                    answer_set.add((nums[idx], nums[left], nums[right]))
                    left += 1
        
        return [list(x) for x in answer_set]

접근 방법

1. nums 리스트를 크기 오름차순으로 정렬합니다.
2. 중복됨을 판단하기 위한 것으로 set을 활용합니다.
3. 나머지 부분의 알고리즘은 두번째의 것과 동일합니다. 다만 3개의 숫자의 합이 0이 되는 경우에는 set 안에 튜플로서 3개의 숫자를 넣습니다.
4. 답안을 출력하는 과정에서 형태에 맞게 변형합니다.

이 알고리즘에서 중복을 제거할 수 있는 이유는 nums의 숫자들이 크기 순서대로 정렬이 되어있기 때문입니다.

 

정렬된 nums = [-4, -1, -1, 0, 1, 2] 라고 가정해보겠습니다.

(index1, index3, index4)의 조합 (index2, index3, index4)의 조합으로 중복으로 존재할 수 있습니다. 이를 set을 활용해 제거합니다.

 

문제의 힌트를 확인했을 때 하나의 고정된 숫자와 나머지 2개의 숫자 조합을 이용해 풀이하는 것 까지는 생각할 수 있었습니다. 하지만, 요소들을 크기 순서대로 정렬시켜 투 포인터 방식으로 3개의 숫자 합이 0인 것을 찾는 방법은 꽤나 신박했던 것 같습니다. 

지금까지 투 포인터 활용 문제를 몇번 마주했는데 나중에 다른 문제를 접할때 투 포인터 방식을 사용할 수 있는지에 대해서도 떠올려볼 수 있을 것 같습니다.