[Leetcode] 3Sum - Two pointer

1.문제

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

 

2.풀이

문제는 세 가지 수의 합이 0이 되는 경우의 수를 모두 구하는건데,

여기서 중복이 없어야한다.

 

리스트가 커져서 그냥 브루트포스로 풀게되면 o(n^3) 으로 너어어무 느려진다.

그래서 좀 더 빨리 풀 수 있는 방법이 투 포인터인데, 왜 투포인터일까?

 

바로 하나를 고정시키고 나머지만 움직이면 되기 때문이다.

투 포인터는 정렬된 배열에서 유용해서 정렬해주는게 좋다.

 

1) 우선 리스트를 순서대로 정렬해줘야한다. 이게 오래걸려보여도 한 번 정렬해주는게 후일을 위해 좋다,, -> O(nlogn) 정도니 할만하다.

2) 이제 세 수를 i, j, k라하면, i를 고정시키는데 nums - 2 까지 돌려야한다. 2개는 나머지 두 포인터를 위해,,

3) i를 첫번째 수로 정하면, 이제 나머지 투포인터들은 그 뒤 숫자, 가장 뒤 숫자로 설정한다.

4) 그리고 세 가지 수를 더하는데, 만약 합 < 0 : j가 작아서 문제라 한 칸 앞 이동 // 만약 합 > 0: k가 너무 커서 문제라 한 칸 뒤 이동

5) 이때 j<k까지만 작동시키고 i를 올리고 썼던 i들은 쳐다도 보지 않으면 된다..

6) 단, 주의할 점이 있다. 내가 간과한 포인트 2개를 설명하자면,
[1] nums 정렬 후 , i, j, k가 이동할때 만나는 중복을 배제안했음 ==> 중복 triple은 배제해야하는 조건
- 코드상 num[i] == nums[i-1] 이런 형태의 부분들이다.
[2] 만약 합이 0이 되어서 저장을 했으면 다음 인덱스를 누가 변해야하는지 문제 ==> 어차피 중복은 배제할거고, 지금 0인데 숫자바뀌면 절대 0될 수 없어서 j,k 둘다 이동해야함

 

## code ##

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        answer = []
        nums = sorted(nums)

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

            j, k = i+1, len(nums)-1

            while j < k:
                sum = nums[i] + nums[j] + nums[k]

                if sum>0:
                    k -= 1
                elif sum<0:
                    j += 1
                   
                else:
                    answer.append([nums[i], nums[j], nums[k]])
                    while j < k and nums[j] == nums[j+1]:
                        j+=1
                    while j < k and nums[k] == nums[k-1]:
                        k-=1

                    j+=1    
                    k-=1 #이게포인트

        return answer

 

+

근데 다쓰고 보니 나왜래 ,, 를 많이쓰지

나이먹어가나봐요 ,,

ㅋㅋ ㅋㅋ