leet code 15 - 3SUM

수상한 제목을 가진 문제.. 

---

파이썬 모듈을 이용한 풀이.

from itertools import combinations

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        #ijk는 서로 다르다. ijk값을 더하면 0이다.
        #똑같은 tripet이 있어서는 안된다.
        # 서로다른 인덱스 세개의 값을 뽑아서 0 이 되게 해라.
        # 똑같은 triplet은 안된다.

        #모든 조합을 구하고
        #구한 조합중 겹치는게 있다면 0으로 만들면 어떨까?

        ls1 = []
        ls2 = []
        for i in combinations(nums, 3):
           ls1.append(sorted(i))

        ls1 = list(map(list,set(map(tuple,ls1))))

        for i in ls1:
            if sum(i) == 0:
                ls2.append(i)

        return ls2

먼저 세수는 모두 다르기 때문에 조합 모듈을 사용해 가능한 조합을 모두 가져왔다.

먼저 콤비네이션으로 뽑힌 튜플들을 정렬해 ls1리스트에 넣어준다.

 

i는 sorted의 결과. 리스트로써 ls1에 들어간다.

 

리스트는 hashable 한 오브젝트가 아니기 떄문에 바로 set 적용이 불가하다. 안의 리스트들을 튜플객체로 바꿔 set연산 적용한 후 list화.

이후 list된 맵 객체들을 다시 list화 한다.

 

이후 ls1을 순회하면서 합이 0인 조합이 있으면 ls2에 삽입한다.

 

 

시간 초과. ls1을 tuple화 하고 list()list() 두번 쓰였기 때문에 콤비네이션의 길이의 세제곱만큼의 시간복잡도를 보인다.

 

---

포인터를 사용한 풀이.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        #인덱스가 중복되지 않게 세개를 뽑는다.  0이되는 것을 반환.

        #모든 조합을 구하고
        #구한 조합중 겹치는게 있다면 0으로 만들면 어떨까?


        res = []
        nums.sort()
        
        for i,a in enumerate(nums):
            if i > 0 and a ==nums[i-1]:
                continue
                
            l, r = i + 1, len(nums) - 1
            
            while l < r:
                threeSum = a +nums[l] + nums[r]
                if threeSum >0:
                    r -= 1
                elif threeSum <0:
                    l+= 1
                else:
                    res.append([a,nums[l], nums[r]])
                    l += 1
                    while nums[l] == nums[l -1] and l < r:
                        l += 1
                        
    
        return res

 

먼저 첫번째로 하는 일은 정렬이다. 포인터를 사용해 일정한 로직으로 문제를 풀려면 정렬을 해줘야 한다.

 

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        #인덱스가 중복되지 않게 세개를 뽑는다.  0이되는 것을 반환.

        #모든 조합을 구하고
        #구한 조합중 겹치는게 있다면 0으로 만들면 어떨까?


        res = []
        nums.sort()
        
        for i,a in enumerate(nums):
            if i > 0 and a ==nums[i-1]:
                continue
                
            l, r = i + 1, len(nums) - 1
            
            while l < r:
                threeSum = a +nums[l] + nums[r]
                if threeSum >0:
                    r -= 1
                elif threeSum <0:
                    l+= 1
                else:
                    res.append([a,nums[l], nums[r]])
                    l += 1
                    while nums[l] == nums[l -1] and l < r:
                        l += 1
                        
    
        return res

첫번째 for문을 사용해 반환에 사용할 인덱스와, 계산에 사용할 값 두개를 선택한다.

세가지 수를 골라야하고, 첫번쨰 포문에서는 첫번째 수를 고른다고 할 수 있는데,  이때 첫번째에 -3이 왔다면, 똑같은 수인 -3이 첫번째에 올수는 없다(중복케이스) 이를 방지하기위해 if문을 설정. 중복 값이라면 해당 순회를 건너 뛴다.

그다음으론 포인터를 사용할 while문을 만들어 준다. 이 조건문에서는 두번째, 세번쨰에 올 수를 고른다.

먼저 어레이를 정렬했기 때문에, 최좌단 값에는 최소값이. 최 우단 값에서는 최대값이 나온다. 그렇기에 0보다 크다면 

우쪽 포인터를 움직여 합을 줄이고, 0보다 작다면 좌측 포인터를 사용해 합을 늘인다. 크기가 값다면 , 결과값 append.

결과 값을 반환한 이후로는 l포인터를 움직여 다음 조합을 탐색한다.

다만 왼쪽 포인터가 첫번째 for문과 마찬가지로, 두번째 값에 중복된 값을 선택할 수 없도록 같은값이라면 조건에 따라 건너 뒬 수 있도록 하는 건너 뛸 수 있게하는 와일 문을 넣는다.

 

다만 우측 포인터에서도 중복값을 선택할 수 있는데 왜 왼쪽 포인터만 옮기는 것일까?

그 이유는 왼쪽 포인터에서만 중복값이 아닌 값으로 바꿔줘도, sum자체가 바뀌기 때문에, 오른쪽에서 중복값을 선택하는것 자체가 문제가 없기 때문.

 

첫번째 for문에서는 continue를 하고, 와일문 안에서는 와일을 사용한건. for문은 자동적으로 1을 증가하는 속성을 가지고 있고,

while문은 아니기 때문..

 

sort 시간복잡도 n log n ,  2중 포문 시간복잡도 n2 

 

n2