문제

주어진 정수 배열 nums안에서 더해서 0이되는 서로 다른 위치에 있는 세 수들을 반환하시오.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Example 2:

Input: nums = []
Output: []

Example 3:

Input: nums = [0]
Output: []

---

풀이

이번 문제는 Two-Pointer방식을 이용하면 생각보다 쉽게 풀 수 있다. 일단 Brute-Force방식을 생각해 볼 수 있지만, 역시나 시간 초과가 난다.

따라서, 먼저 배열을 정렬한 다음, for문을 통해 더해서 0이 될 첫번째 원소를 탐색하면서, 첫 번째 원소 이후의 원소들 중에서 두번째 원소와 세 번째 원소를 찾으면 된다.

여기서 한가지 생각해야 할 것은, 첫번째 보기에서도 나와있듯이, 중복되는 값들이 여러개 제시 될 수 있다. 따라서 첫 번째, 두 번째, 세 번째 원소를 정할 때, 모두 중복을 건너뛰는 코드를 넣어주어야 한다.

또한 놓칠수도 있는 것이, 첫번째 원소와 더해서 0이되는 두 번째, 세 번째 원소의 집합이 2개 이상일 수 도 있다는 것이다. 이러한 것을 생각한다면, 이 문제는 쉽게 해결할 수 있다.

이를 Python으로 구현하면 다음과 같다.

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

        # nums배열 오름차순으로 정렬.
        nums.sort()

        for fst in range(len(nums) - 2):

            # nums에서 중복된 값을 제외하여 fst의 위치를 결정.
            if fst > 0 and nums[fst] == nums[fst - 1]:
                continue

            # sec, trd의 위치를 결정.
            sec, trd = fst + 1, len(nums) - 1

            # 더해서 0이 되는 세 수의 위치를 탐색.
            while sec < trd:
                tot = nums[fst] + nums[sec] + nums[trd]

                if tot < 0:
                    sec += 1

                elif tot > 0:
                    trd -= 1

                else:
                    answer.append([nums[fst], nums[sec], nums[trd]])

                    # fst위치에 있는 수와 더해서 0이되는 중복되지 않는 또 다른 sec, trd의 위치 결정.
                    while sec < trd and nums[sec] == nums[sec + 1]:
                        sec += 1

                    while sec < trd and nums[trd] == nums[trd - 1]:
                        trd -= 1

                    # 이전과 중복된 값에서 벗어나기 위해 sec, trd값을 한번 더 조졍.
                    sec += 1
                    trd -= 1

        return answer

for문 안에 while문이 있고 while문이 하나 더 중첩되어 복잡해 보일 수 있으나, fst와 더해서 0이되는 (sec, trd)가 여러 개일 수 있다는 것만 생각하면 그렇게 어렵지 않을 것이다.