leetcode 15. 3Sum 리트코드 15. 세 수의 합 문제 풀이

<파이썬 알고리즘 인터뷰> 책에서 다룬 리트코드 문제들을 풀이한 포스팅이다.

 

문제는 모두 리트코드에 출제된 문제들이며, 직접 풀었지만, 책에서 주는 힌트와 풀이 과정들을 참고한 경우가 많다.

이곳은  정리한 책에 나온 문제에 대한 목록과 해설을 정리한 공식 깃허브 페이지 이며, 

다음 포스팅은 내가 푼 <파이썬 알고리즘 인터뷰> 문제 풀이 목록을 정리해 놓았다.

 

문제

leetcode.com/problems/3sum

3Sum - LeetCode

입력 : 정수로 된 리스트

출력 : 정수로 된 리스트

 

문제 요약 : 리스트에 있는 원소 중에서 3개를 합쳤을 때 0이 되는 조합을 리스트로 만들어 가능한 모든 경우를 모아 출력

유의 사항 :

1. 효율성이 중요해서, 원소가 3개이기 때문에 반복문을 여러 번 겹쳐서 제출하면 통과되지 않는다.

2. 합이 0이 되는 원소 3개가 담긴 리스트들의 리스트로 제출하는데, 정렬이 되어 있어야 하고, 똑같은 결과가 반복해서 나오면 안된다.

 

생각 과정

처음에는 직관적으로 for 문을 중첩하여 결과가 출력되게 만들었다.

def solution(num):
  result = []
  nums.sort()
  for i in range(len(nums)-1):
      for j in range(i+1, len(nums)):
          third_num = -(nums[i] +nums[j])
          if third_num in nums[j+1:]:
                  num_lst = ([nums[i], nums[j], third_num])
                  if num_lst not in result:
                      result.append(num_lst)
   return result
   
                    

Runtime Error가 떴다.

for 문을 2번 중첩하면 통과할 수 없으므로 1번 이하로 줄여야 하고, for문을 줄이기 위해 while문을 활용해야겠다고 생각했다.

 

기본틀은 이렇게 짰다.

nums.sort()
result = []
for i in range(len(nums)-2):
	left, right = i + 1, len(nums)-1
    while left < right:
        lst_3 = [nums[left], nums[i], nums[right]]
        if sum(lst_3) < 0:
            left += 1
        elif sum(lst_3) > 0:
            right -= 1
        else:
            lst_3.sort()
            result.append(lst_3)
            left += 1
            right -= 1
print(result)
            

 

에러가 발생했고, 책을 참고하면서, 여러 예외 상황을 고려하고,

효율성을 위해 반복을 하지 않도록 짠 코드는 아래와 같다.

풀이

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []
        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:
                lst_3 = [nums[left], nums[i], nums[right]]
                if sum(lst_3) < 0:
                    left += 1
                elif sum(lst_3) > 0:
                    right -= 1
                else:
                    lst_3.sort()
                    result.append(lst_3)
                    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