[Leetcode] 15. 3Sum

✅ 문제 - 세 수의 합

💡 숫자로 이루어진 리스트의 값 3개를 더했을 때 0이 되는 세 수를 구하는 문제

 
 
 

---

 

✅ 첫 번째 시도 - 런타임 초과

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        results = []
        nums.sort()

        #i,j,k 세 수의 합
        for i in range(len(nums)-2):
            
            # 중복값 제외
            if i>0 and nums[i] == nums[i-1]:
                continue

            for j in range(i+1, len(nums)-1):
                if j > i+1 and nums[j] == nums[j-1]:
                    continue

                for k in range(j+1, len(nums)):
                    if k > j+1 and nums[k] == nums[k-1]:
                        continue
                    
                    if nums[i] + nums[j] + nums[k] == 0:
                        results.append([nums[i], nums[j], nums[k]])
        return results

💡 내가 잡은 Point

1. 리스트 오름차순 정렬
2. 세 수 i, j, k 비교
3. 세 수는 중복값이 될 수 없음

---

 
여기서 문제점
for문을 세 번이나 중첩해서 쓰니까 당연히 런타임 에러가 난다. 시간복잡도가 O(N^3) 인 셈.
 

---

 

✅ 두 번째 시도 - 런타임 초과

 
 
solution) 투 포인터 사용

💡투 포인터란? 두 기준점을 잡아(보통은 양 끝) 범위를 점점 좁혀나가며 확인하는 방식

 
 

class Solution:
    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: #합이 0보다 작으면 값이 더 커야하므로 오른쪽으로 이동
                    left+=1
                elif sum>0: #합이 0보다 크면 값이 더 작아야 하므로 왼쪽으로 이동
                    right-=1
                else:
                    results.append([nums[i], nums[left], nums[right]])

        return results

 
중복값 제외하는 것 까지는 똑같고 3개의 중첩 for문 대신 투 포인터 이용하여 left, right를 지정해서 합을 구했는데도 런타임 초과다. 맞는 것 같은데 도저히 답을 모르겠어서 다른 사람들의 풀이를 보니 앞에서 중복값 제거가 한번 더 필요하다.
 
첫 번째로 걸었던 중복값은 바로 앞뒤에 연달아 붙은 값을 비교해서 같은 경우는 넘어가는 것이고,
두 번재 걸어야 할 중복값은 left, right가 이동하면서 같은 값일 경우를 제외하기 위해서다.
 
예를들어 [-3, -2, -2, 0, 1, 2, 2, 3] 일 경우 [-2, 0, 2]가 두 번 나올 수 있다.
따라서 포인터의 앞 뒤 값이 같을 경우는 스킵하고 포인터를 계속해서 다음으로 이동시켜 주면 된다.

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

# while문이 false일 경우 포인터 이동
left += 1
right -= 1

 
while문 밖에서 포인터를 또 이동시켜주는 이유는, 
포인터와 비교하는 수가 달라지게 되면 멈추기때문에 한번 더 이동을 해서 sum을 비교해야하기 때문이다.
 

---

전체 코드

class Solution:
    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: #합이 0보다 작으면 값이 더 커야하므로 오른쪽으로 이동
                    left+=1
                elif sum>0: #합이 0보다 크면 값이 더 작아야 하므로 왼쪽으로 이동    
                    right-=1
                else:
                    results.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