15. 3Sum

Problems

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

세 수의 합이 0 이 되는 조합을 찾을 것.

Solutions

Trials 1

리스트를 순회하면서 조합을 만들어보려고 했다.
itertools.Combination 쓰면 시간초과이므로 for loop를 생각했다.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        
        N = len(nums)
        solutions = []
        
        for i in range(N):
            
            for j in range(i+1, N):
                k = j+1
                
                while k < N:    
                    if nums[i] + nums[j]+ nums[k] == 0:
                        solutions.append([i,j,k])
                        break
                    k += 1

        return solutions

1. 문제에서 요구한 답은 index가 아니고 value다... 정확히 보고 return하자.
2. 중복된 답은 없이 하라고 했다. index로 착각하여 중복은 없을거라했는데 value일 경우 중복답이 발생한다.

intput: [-1,0,1,2,-1,-4]
output: [[-1,0,1],[-1,2,-1],[0,1,-1]]

위 예시처럼 [-1,0,1] 과 [0,1,-1] 은 index 다르지만 value가 같아서 틀린 답이다.

Trials 2

dup = False
for s in solutions:
if s[0] == nums[i] and s[1]==nums[j]:
	dup = True
	break

중복값을 없얘기위해서 if s[0] == nums[i] and s[1]==nums[j] 조건을 추가했는데, 정확히 같은 위치에 있는 원소들끼리 비교하기 때문에 다음 예시에서는 효과가 없었다.

[[-1,0,1],[0,1,-1]]

Trials 3

dup = False
for s in solutions:
    if nums[i] in s and nums[j] in s :
        dup = True
        break

순서와 상관없이 중복값을 거르기 위해 in조건으로 변경하였으나, 하나만 같아도 건너뛰는 부작용이 발생함.
[-2,-4,6]을 먼저 찾은 후 [-2, -2, 4]의 답을 찾는과정에서 기존 답에 -2가 한개만 존재하지만, 조건문이 성립하여 건너 뛰게된다.

Trials 4

애초에 접근법이 완전히 틀렸다.

중복된 답이 없어야 한다.

새로 찾은 답을 기존의 답과 비교하면서 중복을 검증하는 방법과 처음부터 중복된 답을 거르는 방법이 있다. 해당 문제에서의 답은 세가지 원소를 담은 리스트 형태이기때문에 전자의 경우는 직접 비교가 어렵다. 따라서 여기서는 후자의 방식을 택했다.

nums에는 중복된 원소가 존재할 수 있다. 정답 [a,b,c]에서 a와 b가 결정되면 합이 0 이어야하므로 c 도 자동으로 결정된다. 여기서 두 가지 조건을 유추할 수 있다.

1. a고정후 b를 순회하고 c를 순회
2. 처음부터 정렬이되어있다면 간단하게 skip이 가능.

1번 조건에서 3중 반복문을 만들어서 써봤는데 시간초과인거같다.

for i in range(N):
	for j in range(i+1, N):
		k = j+1
		while k < N:   
        	working

merge sorting에서 indexing 했던것처럼 pivot을 두고 left,right로 리스트를 순회하면 훨씬 간단하게 처리할 수가 있다.

p,l,r의 합을 계산했을때 총 세가지 경우의 수가 나온다.

1. 정답인 경우
2. 음수가 나오는 경우
3. 양수가 나오는 경우

각각의 경우에 대해 따로 처리를 해준다.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        N = len(nums)
        nums.sort()
        nums = sorted(nums)
        solutions = []
        for i in range(N-2):
            l = i+1
            r = N-1
            
            if i>0 and nums[i] == nums[i-1]:
                continue
            
            while l<r:    
                s = nums[i] + nums[l]+ nums[r]
                
                if s > 0:
                    r -= 1
                elif s <0:
                    l += 1
                else:
                    solutions.append([nums[i], nums[l], nums[r]])
                            
                    while l<r and nums[l] == nums[l+1]:
                        l= l+1
                    while l<r and nums[r-1] == nums[r]:
                        r= r-1
                    
                    l +=1
                    r -=1
                
        return solutions

솔직히 엄청 어려웠다......