배열 : 세 수의 합(리트코드 15번)

▶ 문제 : https://leetcode.com/problems/3sum/

3Sum - LeetCode

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

##### 입력 #####
# nums = [-1, 0, 1, 2, -1, -4]

##### 출력 #####
# [[-1,-1,2],[-1,0,1]]

 

▶ 접근 방법

1) 브루트 포스로 계산
입력 받은 리스트를 우선 정렬하고, 리스트의 요소를 i, j, k로 하여
세 개의 포인터를 이동시키면서 i + j + k = 0이 되는 값을 찾아낸다.
그런데 중복되는 값이 있을 수 있으므로 해당 경우는 넘어갈 수 있도록 구현한다.

2) 순열로 계산
원소가 3개인 순열 리스트를 만들어서, 해당 리스트의 합이 0을 찾는다.

3) 투 포인터를 이용하여 계산
i를 고정시키고 j, k 값을 투 포인터로 하여 값을 계산한다.

 

▶ 풀이 코드

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

def three_sum(nums: list) -> list:
    result = []
    nums.sort()

    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        for j in range(i + 1, len(nums) - 1):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue
            for k in range(j + 1, len(nums)):
                if k > j + 1 and nums[k] == nums[k - 1]:
                    continue
                if nums[i] + nums[j] + nums[k] == 0 :
                    result.append([nums[i], nums[j], nums[k]])
    return result

print(three_sum(nums))
# [[-1, -1, 2], [-1, 0, 1]]

def three_sum2(nums: list) -> list:
    nums.sort()
    temp = list(combinations(nums, 3))
    result = []
    for i in temp :
        if sum(i) == 0 and list(i) not in result:
            result.append(list(i))
    return result

print(three_sum2(nums))

def three_sum3(nums: list) -> list:
    result = []
    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:
                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

print(three_sum3(nums))

 

▶ 관련 링크

2021.12.15 - [알고리즘/리트코드] - 배열 : 빗물 트래핑(리트코드 42번)