[파이썬 알고리즘 인터뷰][배열] 세 수의 합 (중요)

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

합을 0으로 만드는 3개 엘리먼트 모두 출력

 

책에서 구현된 코드

def threeSum(self, nums: list[int]) -> list[list[int]]:
    results = []
    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 results

 

기억해야할 기법

• 3개의 값을 비교할 때, 1개에 대한 for문 + 투포인터로 O(n²)으로 처리
• 중복된 값을 skip하는 방법을 생각하지 못함
  • for문에서 다음 인덱스 값이 같으면 continue
  • 세 값의 합이 0일 때
    - left / right 모두 같은 값이면 skip
    - skip 후 left / right 모두 한 칸씩 움직이기

 

내가 구현한 코드

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

    if len(nums) < 3:
        return 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:
            all_sum = nums[i] + nums[left] + nums[right]
            if all_sum == 0:
                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
            elif all_sum < 0:
                left += 1
            else:
                right -= 1

    return result

• 투포인터를 활용한다라는 힌트를 보고 작성했는데 모습이 비슷하다