[리트코드] 15. 세 수의 합 (Python)

3Sum - LeetCode

문제

리스트에 있는 숫자 중에서 3개를 합쳤을 때 0이 되는 조합을 리스트로 만들어 모두 출력

과정

1. 입력받은 숫자를 정렬한다.
2. 선택된 원소와 이 전 원소가 중복된 값이면 건너뛴다.  
3. 선택된 원소의 다음 원소와 마지막 원소로 투포인터를 생성해 간격을 좁혀가며 세 수의 합을 계산한다.
4. 0이 나왔을 경우 결과값에 저장해준다.
5. 중복된 결과 값을 방지하기 위해 그 다음 값이 같다면 +1 해준다.
6. 유의사항
       1) 효율성이 중요해서, 원소가 3개이기 때문에 반복문을 여러 번 겹쳐서 제출하면 통과되지 않는다.
       2) 합이 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]]:
        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)
                    left += 1 
                    while nums[left-1] == nums[left] and left < right:
                        left += 1   
        return 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

• 중복된 값은 건너뛰기위해 contine해준다.

left, right = i + 1, len(nums)-1

• 투포인터 생성
• 선택한 값의 그 다음 값과 가장 마지막 값을 비교하며 간격을 좁혀간다.

while left < right:
    lst_3 = [nums[left], nums[i], nums[right]]

• 정렬해 놓았기 때문에 left값이 right 값보다 커지는 순간 모두 확인을 완료한 것이 된다.

if sum(lst_3) < 0:
    left += 1
elif sum(lst_3) > 0:
    right -= 1

• sum() 모든 수의 합
• 합이 0보다 작을 경우 값이 더해져야 하므로 left 위치를 +1
• 합이 0보다 클 경우 값이 적어져야 하므로 right 위치를 -1

else:
    lst_3.sort()
    result.append(lst_3)

• 값이 0이 되는 경우 리스트 정렬후 결과값에 추가

left += 1 
while nums[left-1] == nums[left] and left < right:
    left += 1 

• 중복된 결과 값을 방지하기 위해 그 다음 값이 같다면 +1 해준다.