배열: 세 수의 합

세 수의 합

문제 설명

배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력하라.

def solution(nums):
    ans = []
    nums.sort()
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        start_num = nums[i]
        left = i + 1
        right = len(nums) - 1

        while left < right:
            sum_val = start_num + nums[left] + nums[right]

            if sum_val < 0:
                left += 1
            elif sum_val > 0:
                right -= 1
            else:
                ans.append([start_num, 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 ans

문제 풀이

• brute force로 풀 수 있는 방식이지만 시간 초과 에러가 날 수 있는 문제이다.
• 이 문제를 해결하기 위해서는 투 포인터를 통해서 O(n)으로 해결하는 것이 좋다.
• 문제 해결 방식은 다음과 같다.
  - 세개의 값의 합이 0이 되어야 하기 때문에 하나를 고정하고 투포인터를 적용한다.
  • for문을 통해 하나씩 옮기는 식으로 진행하고, 해당 값 이후의 값을 기반으로 left, right를 정한다.
  • 정해진 값을 기반으로 0보다 작으면 left를 옮기고, 0보다 크면 right를 옮긴다.
  • 그러다가 0이 되면 ans에 값을 넣어주고, 중복된 값이 있을 수 있기 때문에 중복된 값이 아닐때까지 옮겨준다. (left와 right 모두 해당)