세 수의 합

 

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

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

3Sum - LeetCode

 

예제 1.

 

입력

nums = [-1, 0, 1, 2, -1, -4]

출력

[[-1, -1, 2], [-1, 0, 1]]

 

해당 예제를 푸는 것에는 

브루트 포스로도 가능하지만 

시간 복잡도가 O(n^3)으로 되기 때문에 시간 초과가 된다.

 

때문에 다른 방법을 고려 해야하는데 

그중 하나가 투포인터다.

 

퀵 정렬 처럼 왼쪽, 오른쪽 부터 다가오는 포인터로 따로 만들어 시간 복잡도를 획기적으로 줄일 수 있다.

 

풀이 

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

nums = [-1, 0, 1, 2, -1, -4]

def threeSum(nums):
    results = []
    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:
                #sort를 통하여 정렬하였기 때문에 왼쪽 값이 더 작고
                # sum이 0보다 작다는 것은 -1 이하이기 때문에 왼쪽 포인터를 오른쪽으로 한칸 옮김
                left +=1
            elif sum > 0:
                # left를 처리한 방식과 반대
                right-=1
            else:
                results.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  results

print(threeSum(nums))

 

먼저 배열을 정렬 시킨다.

그래야 왼쪽 원소중 하나, 오른쪽 원소 중 하나를 선택하며 0에 맞아 떨어질 확률이 높아진다.

여기서 i와 그 다음 원소인 left, left 원소의 다음인 right를 지정하여 3개의 원소를 한번에 지정한다.

이후 left, right를 한칸 씩 움직이면서 i 번째와의 조합을 전부 확인한다.

 

0이 된다면 배열에 삽입하고, 다시 한번 중복되는 값이 들어오지 않도록 left, right를 조정한다.

이때 두개의 포인터가 서로 엇갈릴 경우를 대비하여 left < right를 지속적으로 확인 해야한다.

 

이 로직을 통하여 O(n^2) 라는 시간 복잡도를 가질 수 있다.