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 이 되는 조합을 찾을 것.
리스트를 순회하면서 조합을 만들어보려고 했다.
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
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가 같아서 틀린 답이다.
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]]
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
가 한개만 존재하지만, 조건문이 성립하여 건너 뛰게된다.
애초에 접근법이 완전히 틀렸다.
중복된 답이 없어야 한다.
새로 찾은 답을 기존의 답과 비교하면서 중복을 검증하는 방법과 처음부터 중복된 답을 거르는 방법이 있다. 해당 문제에서의 답은 세가지 원소를 담은 리스트 형태이기때문에 전자의 경우는 직접 비교가 어렵다. 따라서 여기서는 후자의 방식을 택했다.
nums
에는 중복된 원소가 존재할 수 있다. 정답 [a,b,c]
에서 a
와 b
가 결정되면 합이 0 이어야하므로 c
도 자동으로 결정된다. 여기서 두 가지 조건을 유추할 수 있다.
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의 합을 계산했을때 총 세가지 경우의 수가 나온다.
각각의 경우에 대해 따로 처리를 해준다.
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
솔직히 엄청 어려웠다......