[leetcode 2024/02/05] 15. 3Sum

https://leetcode.com/problems/3sum/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

1. 접근 방법

처음에 접근 했던 방법은 nums를 양수 list와 음수list로 나눈 후, 양수의 2개 값의 합의 *-1 이 음수에 있는지 였다.

이를 음수의 2개 값의 합의 * -1 이 양수에도 있는지 알아보았다.

 

하지만, 이 방법은 잘 풀리다가 뒤쪽 test code에서 runtime error가 났다.

다음을 runtime error가 난 코드이다.

 

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        zeros = 0
        total = set()
        minus = []
        plus = []
        for i in nums:
            if i == 0:
                minus.append(i)
                plus.append(i)
                zeros +=1
            elif i>0:
                plus.append(i)
            else:
                minus.append(i)

        for i in range(0, len(minus),1):
            k = i+1
            while(k!=len(minus)):
                answer = minus[i] + minus[k]
                #print("minus[i]",minus[i])
                #print("minus[k]", minus[k])
                if(answer*-1 in plus):
                    maybe_list = [minus[i],minus[k],answer*-1]
                    maybe_list.sort()
                    if((maybe_list.count(0)<=zeros)):
                        total.add(tuple(maybe_list))
                k+=1

        for i in range(0, len(plus),1):
            k = i+1
            while(k!=len(plus)):
                answer = plus[i] + plus[k]
                #print("minus[i]",minus[i])
                #print("minus[k]", minus[k])
                if(answer*-1 in minus):
                    maybe_list = [plus[i],plus[k],answer*-1]
                    maybe_list.sort()
                    if((maybe_list.count(0)<=zeros)):
                        total.add(tuple(maybe_list))
                k+=1

        return [list(t) for t in total]

 

오랫동안, 고민하다가 다른 코드를 보았다. ㅠ 조금 아쉬우면서도

2개의 pivot을 이용하는 것을 생각하지 못하였다.

 

2개의 pivot을 이용하는 방법은 다음과 같다.

일단 for 문으로, index 0 부터 len(nums)-2 까지 돈다. (-2 까지 도는 이유는 비교하는 값이 3개 필요하기 때문)

이후, i+1 값을 left, len(nums)-1 값을 right로 둔다.

|  (i)  |  (left)  |       |       |       |       |       |       |       |       |  (right)  | 

이런식으로 구성이된다.

만약 i + left + right가 음수라면, left를 한칸 오른쪽으로 옮겨, 0과 값이 가까워지도록 한다.

반대의 경우라면, right를 한칸 왼쪽으로 옮긴다.

 

이를 반복하기 위해, left<right일 때 동안 위 과정을 반복한다.

 

만약 합이 0이 될 경우엔, 해당 값을 list에 따로 넣어준다.

그 과정에서, nums[left] == nums[left +1] 이라면, left를 한칸 더 옮겨 준다.

왜냐하면,  

|  (i)  |  (left)  |       |       |       |       |       |       |       |       |  (right)  | 

이렇게 값을 구한 이후, 

|  (i)  |           |  (left)  |       |       |       |       |       |       |       |  (right)  | 

이렇게 또 값을 구하는 것은 같은 과정을 반복하는 것이기 때문이다. [(left)의 값이 동일한 경우]

-> right도 동일하게 while 문을 돌려준다.

 

따라서 skip  해준다. 

처음에는, 이 방법이 -1, -1, 2 와 같은 경우를 무시하게 되는 것이 아닌가 생각했었다.

하지만, 해당 케이스는 이미, skip 되기 전에 list에 append 되었다. 즉, 이미 고려되었다.

 

또한 다음 for 문을 돌  때, 이전 nums[i] == nums[i-1] 인지 확인해주어, 같은 for 문을 2번 돌지 않도록 한다.

이 또한, -1, -1, 2 와 같은 경우를 무시하는 것이 아닌가 걱정하였지만,

만약 그럴 경우에는, or nums[i] == nums[i+1] 인지도 확인 했을 때이지 않을까 싶다.

 

아래의 경우야 말로, -1, -1, 2를 무시하는 것이 아닌가 싶다.

if i>0 and nums[i] == nums[i-1] or nums[i] == nums[i+1]:
      continue

 

중복되는 지 확인하는 것을 i+1, i-1 둘 중 하나를 기준으로 진행했기 때문에, 

-1, -1, 2 도 고려 가능하다.

따라서, 

nums[i] 가

|        |    (i)    |  (left) |       |       |       |       |       |       |       |  (right)  | 

 

nums[i-1] 과 동일한 경우,

|  (i)  |  (left)  |       |       |       |       |       |       |       |       |  (right)  | 

 

nums[i-1] 에서 nums[i] 의 경우를 이미 계산 완료한 상태이기 때문에, continue를 진행한다.

 

다음에 더 비슷한 문제를 만나게 되면, 더 잘 풀 수 있으리라 생각한다.

 

2. 코드

from typing import List


class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        list = []
        for i in range(0,len(nums)-2, 1):
            if i>0 and nums[i] == nums[i-1]:
                continue
            left = i+1
            right = len(nums) -1


            while(left<right):
                total = nums[i] + nums[left] + nums[right]
                if total < 0:
                    left +=1
                elif total > 0:
                    right -=1
                else:
                    list.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 list



solution = Solution()
print(solution.threeSum([0,-1,-1,2]))