[leetcode / 15] 3Sum

날짜: 2021년 8월 24일
카테고리: 배열
태그: Medium, 15, 파이썬

입출력 예시

예제 입력	예제 출력
nums = [-1,0,1,2,-1,-4]	[[-1,-1,2],[-1,0,1]]
nums = []	[]
nums = [0]	[]

코드

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        answer = []
        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:
                    answer.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 answer

파이썬 알고리즘 인터뷰 7-3

풀이 과정

nums를 풀기 쉽게 정렬하고 시작

nums의 길이 -2 만큼 (세 수의 합이기 때문) 반복

중복된 값이 있을 수 있으므로 조건을 걸고 continue로 띄어 넘어 줌

left에는 i의 다음 인덱스를 저장하고 right에는 nums의 마지막 인덱스를 저장

sum에는 num에서 i인덱스의 원소, left인덱스의 원소, right인덱스의 원소의 합을 저장

left가 right보다 커질 때까지 조건에 따라 반복

sum이 0보다 작을 경우 : left += 1 (left를 오른쪽으로 이동)
sum이 0보다 클 경우 : right -= 1 (right를 왼쪽으로 이동)
sum이 0일 경우 :
- answer에 num에서 i인덱스의 원소, left인덱스의 원소, right인덱스의 원소를 원소로 갖는 배열 저장
- 왼쪽 인덱스(오른쪽 인덱스)에 중복 된 원소의 존재 유무를 while문으로 확인하고 있다면 왼쪽(오른쪽)으로 시프트
- 다음 연산을 위해 left += 1 (left를 오른쪽으로 이동), right -= 1 (right를 왼쪽으로 이동)

위의 과정을 반복 후 answer 반환

반성

문제를 보았을 때 투 포인터로 접근하면 된다는 생각까지는 들었으나 투 포인터를 응용해서 문제를 풀이하는 데 까지는 사고가 되지 않았다. 수학 문제 처럼 한 유형의 문제를 완벽하게 하기 위해서는 많이 풀어보는 수 밖에 없는 것 같다.