leetcode 15 (medium)

문제

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

풀이 1

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        d = defaultdict(list)
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                d[nums[i]+nums[j]].append([[nums[i],nums[j]],[i,j]])
        
        
        answer = []
        for i in range(len(nums)):
            if -nums[i] in d:
                for j in d[-nums[i]]:
                    if i not in j[1]:
                        answer.append(sorted(j[0]+[nums[i]]))
      
        answer2 = []
        
        for l in answer:
            if l not in answer2:
                answer2.append(l)
                
        return answer2

3개의 합을 for문으로 돌리면 O(n^3)이 되어 문제 인풋 범위가 3천까지이기에 시간초과가 될것이므로
O(n^2) 으로 줄일 수 있는 방법을 고민해봤다.

처음 생각한 방법은 2번만 돌려서 n^2의 값을 dict로 저장해두고 다시 O(n)만큼만 돌리면서 합이 0이되는 경우가 있는지 체크하고 그에따라 처리하는 방식을 생각했다.

하지만 중복제거나 여러가지 상황을 신경쓰다보니 뭔가 복잡해졌고 시간초과가 났다.
논리 자체는 이렇게 해도 되는것같다. dict로 만들어 저장하면 거의 접근 자체는 O(1)로 가능하기에 n^2 + n이 되어 최종적으로 n^2으로 처리할 수 있지 않을까 생각해봤던 접근이었는데 잘 안됐다.

사실 그냥 다른 방법으로 풀어볼까 싶었지만, 뭔가 오기가 생겨서 한참 끄적이다보니 이렇게 되버렸다
지금 너무 졸려서 눈에 안들어오는 관계로 이 풀이를 최적화 시켜 풀어낼 수는 없는지 내일 이어서 고민해봐야겠다

풀이 2

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        answer = []
        nums.sort()
        for i in range(len(nums)-2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
                
            left = i+1 
            right = len(nums)-1
            
            while(left < right):
                summ = nums[i] + nums[left] + nums[right]
                if summ < 0:
                    left += 1
                    
                elif summ > 0:
                    right -= 1
                    
                else :
                    answer.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 answer

for문으로 한번 돌리면서 투포인터를 돌리는 방식이다.
O(n^2) 정도로 될것같다
미리 정렬을 하기위해 sort 과정을 거치지만 sort는 nlogn으로 가능하므로 상관없을것이다
중복제거를 위해서 중간중간에 다음 배열값과 값이 같으면 넘어가는 코드를 추가해주었다.

마지막에 한번에 중복처리를 해줘되 되지만, 배열형식은 list(set(answer)) 가 안먹기 때문에
한번에 제거하기도 힘들고, 불필요한 탐색은 패스할 수 있으면 아예 패스하는게 빠를것 같아서 미리미리 체크하게끔 했다.

결과