15. 3Sum

합이 0 되도록 하는 세 숫자의 조합을 나열하는 문제이다.

 

left, right index를 사용하는 문제가 떠올라서 그 방법으로 접근하였다.

 

하지만, 예외가 발생하였다.

 

ex) -2 0 1 1 2 일 경우에 처음에 (-2, 0, 2) 조합을 찾은 후, left 인덱스를 ++해주면 (-2,1,1)이란 답이 발생될 수 없게 된다.

만약 right 인덱스를 ++해주면 위 예제와 반대의 경우에 발생될 수 없다.

그래서 위 두가지 경우를 모두 해줄 수 있도록 index 변화값만 바꿔서 두번 하게 하였으나, 이 또한 여러개가 중첩적으로 발생할 경우, 안되는 것을 보았다.

 

문제점을 곰곰히 생각해보니, 세 수를 한꺼번에 컨트롤 하려는 것이 문제였다. 세가지 숫자에서 두가지 숫자를 고정하고 한가지 숫자를 찾으려 했지만, 두가지 숫자를 한꺼번에 컨트롤 할 수 없었다.

거꾸로, 한가지 숫자를 우리가 움직이도록 하고, 나머지 두가지 숫자의 조합을 찾는 것이 더 수월해보였다.

따라서 for문으로 i를 바꾸어가며 고정시키고, i 보다 오른쪽의 숫자 중 0이 되도록 하는 나머지 두 개의 숫자쌍을 찾는 방식으로 풀었다.

 

그러기 위해서는 무조건 처음에 nums 배열을 정렬시켜야하고, 중복되는 답을 없애기 위해 result를 집합 자료형으로 만들고 그곳에 add를 한다.

 

 

결론적으로 right, left 인덱스를 사용하는 방법은 맞았으나, 한 가지 숫자를 고정시켜야 했다.

 

 

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