리트코드(LeetCode) 15번 세 수의 합(3 Sum)

---

 

 

📌  풀이 1 : 브루트 포스

가장 먼저 생각 난 풀이는 브루트 포스이다.

하지만 세 수를 비교하는 문제이기 때문에 for문을 3번이나 돌리게 돼서 시간 복잡도는 O(N^3)이 된다.

num.length의 범위가 3000까지 이므로 이 시간 복잡도로는 시간 초과가 나오게 된다.

 

 

그래도 풀이과정을 소개하자면

• 처음 i 일 때는 len(nums)-2까지
• 다음 j 일 때는 i+1부터 len(nums)-1까지
• 마지막 k 일 때는 j+1부터 len(nums)까지

for문을 돌려가면서 nums [i]+nums [j]+nums [k] == 0 가 된다면

arr 리스트에 [nums [i], nums [j], nums [k]] 를 append 해주는 것이다.

이때 앞뒤로 같은 값이 있을 경우를 처리해주기 위해 처음에 nums를 정렬해주고 앞 뒤 값을 비교해 중복 값이 있는 경우 continue로 넘겨준다.

 

 

 

브루트 포스 풀이 코드

arr = []
nums.sort()
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:
                arr.append([nums[i], nums[j], nums[k]])
return arr

 

 

 

 

 

 

📌  풀이 2 : 투 포인터 풀이

우선 i를 축으로 하고 앞 뒤 중복 값을 넘겨준다.

(이때 nums [ i ] == nums[ i+1 ]로 비교하게 되면 index를 벗어나게 되니 조심하자)

for i in range(len(nums) - 2):
	if i > 0 and nums[i] == nums[i-1]:
    	continue

 

 

 

이제 투 포인터를 사용하기 위해 nums를 정렬해주고 left와 right를 지정해준다.

여기서 left와 right는 index이다.

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

 

이제 while문을 사용하여 두 개의 포인터가 만날 때까지 반복을 돌려주며 

sum_num = nums [i] + nums [left] + nums [right]에서 

sum_num 이 0보다 작다면 left를 오른쪽으로 이동해주고 

sum_num이 0보다 크다면 right를 왼쪽으로 이동해준다.

(이 과정은 nums가 정렬돼 있기 때문에 가능한 것이다.)

 

 

마지막으로 sum_num이 0이 되는 경우 arr에 추가해주는데 여기서 조심할 점은 left, right의 앞 뒤로 같은 값이 있는 경우

답이 중복돼서 나올 수 있으므로

(예를 들어 [-2, -1, -1, -1, 0, 3, 3, 3, 4] 인 경우 [-2, -1, 3]이 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

해준다.

 

 

 

투 포인터 풀이 코드

arr = []
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_num = nums[i] + nums[left] + nums[right]
        if sum_num < 0:
            left += 1
        elif sum_num > 0:
            right -= 1
        else:
            arr.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 arr