[TIL]LeetCode#15

15. 3sum

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

입력

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

출력

[[-1,-1,2],[-1,0,1]]

풀이

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
    	result = []
        # 입력 받은 배열을 오른차순으로 정렬
        nums.sort()
        # 한 요소를 고정시키고 투포인터를 쓰기 때문에 -2를 한다.
        for i in range(len(nums)-2):
        	# 중복 제거
        	if nums[i] == nums[i-1]:
            	continue
            # 투포인터 설정
           	left, right = i + 1, len(nums) - 1
            
            # 투포인터
            while left < right:
            	# 세 숫자의 합
            	sum = nums[i] + nums[left] + nums[right]
                # 0보다 작으면 left 포인터를 이동
                if sum < 0:
                	left += 1
                # 0보다 크면 right 포인터를 이동
                elif sum >0:
                	right -= 1
                # 0인 경우
                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
                

로직

임의의 배열을 받았을 때, 우선적으로 배열을 정렬한다. 정렬된 배열에서 첫 번째 요소의 인덱스에 1을 더한 후 투 포인터로 합을 구한다. 합이 0이되면 세 숫자를 하나의 리스트로 결과값에 추가한다.

느낀점

처음에 문제를 가볍게 생각하고 for 반복문을 세개 겹쳐서 풀이를 해보았지만 결과적으로 타임 오버가 통과하지 못했고 중복된 값을 제거하는데 어려움이 있었다. 투포인터를 사용하니깐 런 타임 관련된 문제도 해결되었고 중복제거에도 수월해졌다.

추가 잡담 ) while문도 많이 쓰다보니 조금씩 익숙해지고 있다.