[ LeetCode - 15 ] 3Sum

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

3Sum - LeetCode

유사한 유형의 문제로 백준의 세 용액과 비교해 볼 수 있을거 같다.

 

[ 📌 풀이 ]

1. 이진 탐색을 수행하기 위해서 리스트 정렬을 수행한다.
2. 리스트를 순회하면서 현재 순회하는 인덱스를 'i' 라고 한다.
3. 'i'를 기준으로 다음 인덱스인 left와 마지막 인덱스를 right라고 두고 이분탐색을 시행한다. 

 

이진 탐색을 수행하지만 총 3개의 값의 합이 필요하기 때문에 하나의 수를 'i'로 설정하여 리스트를 순회하고, 나머지 두 수를 앞과 뒤로 설정하여 해당하는 값이 나오면 answer 리스트에 넣는 방식이다.

 

[ 📌 코드 - Python ]

class Solution(object):
    def threeSum(self, nums):
        answer = []
        nums.sort()
        length = len(nums)

        for i in range(length):
            left = i + 1
            right = length - 1

            while left < right:
                sum = nums[i] + nums[left] + nums[right]

                if sum == 0:
                    answer.append((nums[i], nums[right], nums[left]))
                    right -= 1
                    left += 1
                elif sum > 0:
                    right -= 1
                else :
                    left += 1

        return set(answer)