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. 정수 배열 nums에서 i != j, i != k, j != k 이면서 nums[i] + nums[j] + nums[k] == 0를 만족하는 모든 Triplets를 return하라.
Notice that the solution set must not contain duplicate triplets. 솔루션 세트에는 중복된 Triplets이 포함되어서는 안된다.
🔍Institution
문제 조건
i, j, k는 서로 달라야 함
3개를 더해서 0을 만족하는 리스트를 반환
중복이 되면 안 됨
무슨 유형일까?
brute force → 3중 for문으로 해야 함 → 비효율적이므로 하지 않을 거임
two pointer : left, right와 새로운 변수를 하나 활용하여 값을 비교한다면 반복문을 하나 줄일 것으로 판단함 ⇒ two pointer로 풀 예정!
삽질1: two_sum 변수 안에 연속되는 2개의 인덱스의 값을 넣은 후, left와 right로 비교→ 모든 케이스를 커버할 수 없음
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
answer = []
left = 0
right = len(nums)-1
sorted(nums)
while left < right:
two_sum = nums[left] + nums[left+1]
if two_sum + nums[right] == 0:
if two_sum + nums[right] is not answer:
answer.append([nums[left], nums[left+1], nums[right]])
left += 1
elif two_sum + nums[right] < 0:
right -= 1
elif two_sum + nums[right] > 0:
right -= 1
return answer
→ 모든 케이스를 커버할 수 없음
삽질2
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
answer = []
left = 0
right = len(nums)-1
sorted(nums)
target = 0
while left < right:
target = - (nums[left] + nums[right])
for i in range(left, right):
if nums[i] == target:
answer.append([left, target, right])
left += 1
right -= 1
if target < 0:
left += 1
return answer
위의 삽질의 결과는 “시간초과”와 “모든 경우의 수를 탐색하지 않은 것”이었다. => 즉, 시간초과가 되지 않으면서 “모든 경우의 수"탐색할 수 있어야 한다.
새로 풀이한 방식은 하나의 fix값을 고정한 후, 나머지에서 left와 right를 설정하여 투포인터 방식으로 풀이하는 것이다.
Flow
for문을 i=1부터 nums리스트 길이까지 반복한다.
fix변수는 for문 안에서 i의 값에 따라 고정하는 변수이다. 즉 fix = nums[i] 값을 저장한다. left의 값은 i의 다음이 되어야 한다. i와 같거나 i=0부터 시작한다면 이전에 봤던 것과 겹치기 때문! right의 값은 투포인터의 정석대로 가장 마지막 인덱스 값을 넣어주어야 한다. fix = nums[i]
left = i + 1
right = len(nums) - 1
이후 left가 right랑 같지 않을 동안 반복한다.
fix값과 nums[left], nums[right]를 모두 더한 값이 0인 경우,
answer에 [fix, nums[left], nums[right] 가 존재하지 않다면 ⇒ [fix, nums[left], nums[right]을 append한다.
이때, 0인 경우가 나왔을 때 break하는 것이 아니라 다음으로 바로 넘어간다 (left += 1)
fix값과 nums[left], nums[right]를 모두 더한 값이 0보다 작은 경우,
⇒ left값을 +1 한다.
fix값과 nums[left], nums[right]를 모두 더한 값이 0보다 큰 경우,
⇒ right값을 -1한다.
최종 코드
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
answer = []
left = fix = 0
right = len(nums)-1
nums = sorted(nums)
for i in range(len(nums)):
fix = nums[i]
left = i + 1
right = len(nums) - 1
while left < right:
if fix + nums[left] + nums[right] == 0:
if [fix, nums[left], nums[right]] not in answer:
answer.append([fix, nums[left], nums[right]])
left += 1
elif fix + nums[left] + nums[right] < 0:
left += 1
elif fix + nums[left] + nums[right] > 0:
right -= 1
return answer
고려해야 할 상황
모든 테스트케이스는 다 통과했으나, submit했을 때 새로운 테스트케이스에서 오류가 났음
[0,0,0,0]에서 time limit가 뜸
fix = 0, left = 0, right = 0 임 ⇒ 이것 때문에 0,0,0,0인 경우를 따로 만들었음
즉, answer리스트에 있는지 없는지 판단하는 것이 필요함
[-2,0,1,1,2]가 들어오면 output 으로 [[-2, 0, 2], [-2,1,1]] 이 나와야 하는데 내 출력값은 [[-2,0,2]]만 나옴
이 말은 즉슨, fix가 같은 값일 때 하나의 답만 나오는게 아니라 여러 값이 나올 수도 있다는 것을 의미함
즉, append한 조건문에서 break나 return을 하면 안 된다는 것을 의미함!!
그럼 어떻게???
fix한 값에서 다음 left값에서도 정답이 나올수도 있는거니까, 다음으로 넘어가야 함 left += 1하면 됨
정리
answer리스트에 이미 있는지 없는지 판단 ⇒
if [fix, nums[left], nums[right]] not in answer:
fix한 값 안에서도 여러 정답이 나올 수 있으므로, break가 아닌 다음 값으로 넘어가기
if fix + nums[left] + nums[right] == 0:
if [fix, nums[left], nums[right]] not in answer:
answer.append([fix, nums[left], nums[right]])
left += 1
🚩My submission
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
answer = []
left = fix = 0
right = len(nums)-1
nums = sorted(nums)
for i in range(len(nums)):
fix = nums[i]
left = i + 1
right = len(nums) - 1
while left < right:
if fix + nums[left] + nums[right] == 0:
if [fix, nums[left], nums[right]] not in answer:
answer.append([fix, nums[left], nums[right]])
left += 1
elif fix + nums[left] + nums[right] < 0:
left += 1
elif fix + nums[left] + nums[right] > 0:
right -= 1
return answer
시간 복잡도 : O(NlogN)
보통 투 포인터로 풀게 된다면while 조건문이 left < right이므로 --> O(logN)
근데 이 문제는 투포인터를 nums의 길이만큼 반복(for 문) 하기 때문에 --> O(NlogN)
🚩Others submission
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
answer = []
nums.sort()
for i, a in enumerate(nums):
if i > 0 and a == nums[i-1]:
continue
left, right = i+1, len(nums)-1
while left < right:
sum3 = a + nums[left] + nums[right]
if sum3 > 0 :
right -= 1
elif sum3 < 0:
left += 1
else:
answer.append([a, nums[left], nums[right]])
left += 1
while nums[left] == nums[left-1] and left < right:
left += 1
return answer
코드 설명:
if i > 0 and a == nums[i-1]:
continue
이 부분의 코드를 추가하면 시간을 더 효율적으로 쓸 수 있다고 함
실제로 보았을 때 위 코드는 955ms가 뜨고, 내가 짠 코드는 6561ms가 되는 것으로 보아 훨씬 효율적인 것으로 볼 수 있다.
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
answer = []
nums.sort()
len_nums = len(nums)
for i in range(0, len_nums-2):
for j in range(i+1, len_nums-1):
for k in range(j+1, len_nums):
if nums[i] + nums[j] + nums[k] == 0:
if [nums[i], nums[j], nums[k]] not in answer:
answer.append([nums[i], nums[j], nums[k]])
return answer
💡TIL
다음으로 넘어갈 때 바로 break시키는 게 아니라 테스트케이스를 확인해야 함!!
sorted함수 쓰면 대입을 해줘야 함.. 바보바보..
fix 부분 // 내가 짠 거에 헷갈렸음.. nums[fix]가 아님 fix = nums[i] 로 했으니까 그냥 fix만 넣어도 되는거임
투포인터를 2개의 값만 비교했었는데 3개의 값을 비교할 때는 어떤 방식으로 접근하면 되는지 다양한 방식으로 사고할 수 있었다. (물론 지금 정리한 방식 말고 나머지 2개는 모든 경우의 수를 다루지 않은 경우긴 했다..)
