[Leetcode 아주 상세한 문제풀이] 15. 3 Sum - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 15번 문제 3 Sum 이다.

우선 문제를 살펴보자.

 

리트코드 15번 문제 3 Sum (링크)

3Sum - LeetCode

3Sum - LeetCode

 

 

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

 

 

문제 설명

문제에 대해 간략히 살펴보자.

우선 integer로 이루어진 배열 (array) 이 주어진다.

이 integer array 안에서 3개의 숫자를 골랐을 때 그 합이 0이 되는 모든 숫자 조합을 고르라는 문제다.

단, 중복된 숫자 조합은 피해야 한다.

문제 예시 1번 처럼 인풋으로 [-1,0,1,2,-1,-4]가 주어졌다고 생각해 보자.

여기서 3개의 숫자를 고르는 경우는 그 조합의 수가 굉장히 많을 것이다.

이때 고른 3개의 숫자의 합이 0이 되는 숫자 조합을 모두 찾는 문제다.

접근법이 조금 어려울 수 있다.

하지만 문제 자체는 매우 간단하니 곧바로 문제를 풀어보도록 하자.

 

 

문제 접근법

우선 가장 직관적으로 생각할 수 있는 접근 방법은 주어진 integer array에서 숫자 3개를 고르는 모든 조합을 탐색하는 것이다.

숫자 3개를 골라 그 합이 0이 되는지 아닌지 판단하면 된다.

하지만 이 방식의 경우 time complexity가 O (n^3)이 되기 때문에 굉장히 비효율적인 접근법이라 할 수 있다.

좀 더 효율적인 접근 방법은 주어진 integer array를 먼저 오름차순으로 정렬 (ascending sort) 하는 것이다.

그러면 큰 장점이 하나 생기게 되는데, 문제 example 1의 경우 integer array를 정렬하면 아래와 같다.

이때 3개의 숫자 조합 중 1가지를 fix하고 (= -4) 나머지 2개의 숫자를 left, right 포인터를 사용해 탐색한다.

이 방식의 장점은 left와 right를 효율적으로 옮기며 탐색할 수 있다는 점이다.

예를 들어 현재 상황에서 세 숫자의 합은 -3 (= -4 + -1 + 2)다.

우리가 찾고자 하는 것은 세 숫자의 합이 0이 되는 경우이기 때문에 left 포인터를 오른쪽으로 한 칸 옮겨 탐색해야 한다.

Right 포인터를 왼쪽으로 한 칸 옮겨 탐색할 경우 (e.g., 2 -> 1) 세 숫자의 합이 같거나 더 작아지기 때문이다.

결국 이 방식도 O (n^2)의 time complexity를 가지긴 한다.

하지만 모든 숫자 조합을 탐색해야 하는 brute force 방식보다는 효율적이라고 할 수 있다.

이제 코드로 살펴보자.

 

 

문제 풀이

우선 integer array을 받을 함수를 정의해 주고 그 배열을 오름차순으로 정렬해준다 (line 1-2)

그리고 입력받은 배열의 길이 -2 만큼 for loop를 돌려준다 (line 6)

n-2 인덱스에 위치한 숫자가 fix 되면 배열의 마지막에 위치한 두 숫자는 자동 고정되기 때문이다.

그리고 i>0에 대하여 그 직전에 탐색한 숫자와 현재 인덱스에 위치한 숫자가 같을 경우 continue로 for loop을 건너뛴다. (line 8-9)

문제 조건에서 duplicate triplets이 없기 때문이다.

 

예를 들어 입력된 array가 [-1, -1, 0, 1]이라면, line 8-9가 없을 경우 [-1, 0, 1], [-1, 0, 1]을 두번 출력한다.

첫번째 리스트에서 -1은 index=0, 두번째 리스트에서 -1은 index=1에 해당하는 -1이다.

Left 포인터는 현재 fix한 인덱스 보다 한 칸 오른쪽에 (line 11), right 포인터는 배열 끝에 위치시킨다 (line 12)

그리고 left 포인터가 right 포인터보다 왼쪽에 위치하는 한 while loop를 돌리는데 (line 14)

우선 현재 fix한 인덱스의 값과 left, right 포인터가 위치한 값들의 합을 구해 (line 15)

만약 그 합이 0이라면 우리가 찾는 숫자 조합이기 때문에 결과를 출력할 triplets에 추가해주고 (line 18)

 

위해서 설명한대로 세 숫자의 합이 0보다 작다면 left 포인터를 오른쪽으로 한 칸 (line 28-29)

세 숫자의 합이 0보다 크다면 right 포인터를 왼쪽으로 한 칸 옮긴다 (line 30-31)

이 때 중복된 조합을 피하기 위해 left포인터의 숫자와 그 다음에 올 숫자

그리고 right 포인터와 그 다음에 올 숫자가 갔다면 각 포인터들을 한 칸식 더 옮긴다 (line 21-24)

마지막으로 우리가 원하는 숫자 조합이 들어있는 triplets을 return 한다.

 

 

문제 풀이 코드

def threeSum(nums):
    nums.sort()  # Sort the array in ascending order
    n = len(nums)
    triplets = []
 
    for i in range(n - 2):
        # Skip duplicates for i
        if i > 0 and nums[i] == nums[i - 1]:
            continue
 
        left = i + 1
        right = n - 1
 
        while left < right:
            target = nums[i] + nums[left] + nums[right]
 
            if target == 0:
                triplets.append([nums[i], nums[left], nums[right]])
 
                # Skip duplicates for left and right
                while nums[left] == nums[left + 1]:
                    left += 1
                while nums[right] == nums[right - 1]:
                    right -= 1
 
                left += 1
                right -= 1
            elif target < 0:
                left += 1
            else:
                right -= 1
 
    return triplets
 
# Example usage
nums = [-1, 0, 1, 2, -1, -4]
print(threeSum(nums))

 

15. 3 Sum