[LeetCode] 4. 세 수의 합

LeetCode 15번 문제는 포인터라는 개념을 이용해서 문제를 풀이한다. 우선 문제풀이는 아래와 같다.

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

        nums.sort()
        result = []

        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:
                    left += 1
                elif sum > 0:
                    right -= 1
                else:
                    result.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 result

 

세개의 숫자를 합하여 0이 되어야하기 때문에 직관적으로 생각나는 방법은 삼중 for문을 사용하는것이다. 하지만 이럴경우 시간복잡도 $O(N^{3})$이 되기 때문에 효율적이지 못하다. 따라서 이럴경우는 입력리스트의 앞쪽과 뒤쪽에서 차례대로 값을 뽑아 비교하는 방법이 존재한다.

 

당연하게도 입력된 리스트를 오름차순 정렬하는것부터가 시작이다. 정렬하지 않는다면 굉장히 복잡해진다.
일단 리스트 탐색을 하는경우 정렬을 해보자 라는것을 머리속에 떠올리도록 하자.

 

정렬을 한 이후에는 리스트에서 맨앞쪽 값을 고정하고 나머지 인덱스를 투포인터로 탐색하는 방법이다.

 

 

이제 왼쪽 포인터는 오른쪽으로, 오른쪽 포인터는 왼쪽으로 움직이면서 리스트를 탐색해야한다. while 반복문을 사용하여 각각의 포인터를 이동하면서 모든 값을 탐색할 수 있다.

 

이제 두 포인터와 고정된 값을 더하여 그 값을 0보다 큰지 작은지를 검사한다. 0보다 작다면 왼쪽포인터를 오른쪽으로 이동시키고 크다면 오른쪽포인터를 왼쪽으로 이동시키면 된다. 0이라면 result 변수에 결과를 저장한다.

 

문제를 풀면서 어려웠던 부분은 그 다음이다.

 

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

 

이 부분은 중복이 되는 영역을 건너뛰기 하는부분을 뜻한다. -2와 4는 중복이 되기때문에 중복이 발생하지 않는 곳까지 포인터를 이동시켜주어야 한다.

 

1회 시행 후 포인터를 옮기면 다음 시행의 While 조건이 False가 되어 탈출하게 된다. 그러면 현재 포인터의 위치는 아래 그림과 같이 빨간색에서 멈춰있다는 것이다. 하지만 우리는 포인터를 -1이 있는곳까지 이동시켜야 하기 때문에 마지막에 left += 1을 해줘야만 한다. 오른쪽 포인터도 마찬가지 방법으로 시행해야한다.

 

 

또한 While문에는 left < right라는 조건도 있는데, 바로 아래와 같은 예외케이스가 존재하기 때문이다.

 

 

이와 같은 작업을 고정된 값을 오른쪽으로 이동시키면서 반복해주면 시간복잡도 $O(N^{2})$로 해결할 수 있다.