[리트코드] 3Sum(python)

리트코드, 3Sum_세 수의 합

 

TL;DR

• 투 포인터(two pointer)를 활용한 배열 문제

문제 분석

1. 주어진 숫자 배열에서, 세 수를 더해서 0이 되는 세 수를 배열에 담아 반환하라.
2. 단, 이 때, 세 수의 인덱스가 같으면 안된다.(i != j, i != k, j != k)
3. 동일한 세 수의 쌍이 배열에 담기면 안 된다.

 

- 1 ~ 2 : 해결해야 하는 문제에 대해서 설명하고 있다.

- 3 : 문제 해결 시 주의사항에 대해서 설명하고 있다.

    - 예를 들어, [0, 0, 0, 0, 0, 0]이 주어졌을 경우 [[0, 0, 0], [0, 0, 0]]과 같이 저장이 되어야 한다.

    - 이 때, 각 0의 인덱스가 모두 달라야 한다. 같은 인덱스를 참조하여 넣은 답일 경우 오답이 된다.

입출력 형태

입출력 예시

 

- nums : 숫자가 들어있는 배열이다. 길이는 0 이상 3,000이하이며, 배열 내의 숫자들은 -10^5이상 10^5 이하이다.

    - 브루트 포스로 풀 경우에는 3개의 인덱스를 표현하는 변수를 사용해야 하는데, 이 때, 시간 복잡도는 O(n^3)이다.

    - 3,000^3은 1억을 넘어가기 때문에 브루트 포스로 풀 경우 시간 초과로 문제를 통과하지 못한다.

- 예시 1

    - 주어진 배열  nums에서 더해서 0이 되는 경우는 [-1, -1, 2], [-1, 0, 1]이 된다. 따라서 해당 배열들을 반환한다.

- 예시 2, 3

    - 더해서 0이 되는 세 수가 없기 때문에 빈 배열 []을 반환한다.

풀이

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # exception
        if len(nums) < 3:
            return []
        
        answer = []
        nums.sort() # 1. 수를 먼저 정렬한다.
        
        # two pointer
        for i in range(len(nums) - 2):
            if i > 0 and nums[i - 1] == nums[i]: # 2. 동일한 원소가 붙어 있는 경우 넘어간다.
                continue
                
            left, right = i + 1, len(nums) - 1
            
            while left < right:
                sums = nums[i] + nums[left] + nums[right]
                if sums < 0: # 3. 합이 음수일 경우
                    left += 1
                elif sums > 0: # 4. 합이 양수일 경우
                    right -= 1
                else:
                    answer.append([nums[i], nums[left], nums[right]])
                    
                    # 2. 동일한 원소가 붙어 있는 경우 넘어간다.
                    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 answer

 

- exception : 예외 처리를 먼저 해준다. 예시 2, 3번과 같이 배열 내 원소의 길이가 3이 되지 않는 경우는 배열 내에 어떤 숫자가 있더라도 문제에서 제시하는 조건을 만족할 수 없으므로 빈 배열 []을 반환한다.

 

- 1. 배열 정렬 :

    - 배열을 정렬하는 이유는 투 포인터를 적용하기 위해서이다. 가장 작은 값과 가장 큰 값을 양 끝 단에 두고 점점 범위를 좁히며 0이 되는 경우를 찾는다.

- 2. 동일한 원소가 붙어 있는 경우 넘어간다. :

    - 예시 1에서 제시된 배열을 정렬할 경우, [-4, -1, -1, 0, 1, 2]가 된다.

    - 이 때, 주의해야 하는 문제 조건이 바로 2번이다. 이 조건을 유의하지 않을 경우 가장 먼저 나오는 1번 인덱스의 -1이 두번 쓰여 문제 정답이  [[-1, -1, 2], [-1, -1, 2], [-1, 0, 1], [-1, 0, 1]]과 같이 중복되어 출력될 수 있다. 첫 번째 경우는 1번 인덱스의 -1을 조회한 경우이고, 두 번째 경우는 2번 인덱스의 -1을 조회한 경우이다.

- 3. 세 수의 합이 음수일 경우에 right를 좁히며 더하더라도 음수가 나온다. 그렇기 때문에 이 때는 left의 범위를 좁혀준다.

- 4. 세 수의 합이 양수일 경우에 left를 좁히며 더하더라도 양수가 나온다. 그렇기 때문에 이 때는 right의 범위를 좁혀준다. 3번과 4번을 위해서 가장 최초에 주어진 배열을 오름차순으로 정렬한다.

- 이후, 문제 조건에 따라 합이 0이 될 경우 정답 배열에 담아서 반환한다.