투 포인터 응용하기 (3Sum)
투 포인터 응용하기 (3Sum) — #LeetCode #3Sum #개발자의도구들 #투포인터 only 파이썬 목표 참고 : 여기 전략 생각하기 O(n³)로 구...
#LeetCode#Naver Blog
#LeetCode #3Sum #개발자의도구들 #투포인터
- only 파이썬
- 목표 참고 : 여기
전략 생각하기
LeetCode(medium 15. 3Sum) 36.4%
⚠️ 입력값 : num.length = 1000
>>> O(n³) 가능?
>>> 1000 * 1000 * 1000 = 10억
>>> 되려나 ??
O(n³)로 구현해보기
입력값이 1000이라서 안될 것 같긴하지만, 그래도 시도해보자.
✅ for문 3개 돌리자.
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
result = []
n = len(nums)
test = 0
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
test += nums[i] + nums[j] + nums[k]
print("now: i, j, k", (i, j, k))
print("value: nums[i~k]", (nums[i], nums[j], nums[k]))
print("test: ", test)
if test == 0:
result.append([nums[i], nums[j], nums[k]])
test = 0
return result
- 가장 간단하고 빠르게 구현이 가능했다.
- ❌ 문제가 생겼다.
- 정답에서 요구하는 것은
- \[-1, 0, 1\]과 \[1, 0, -1\]을 동일 값으로 보고 하나를 제거해야한다.
- set을 사용해야할까?
- 하지만 set은 List를 hash 할 수 없다.
list의 중복을 확인하기
🗝️ 이번 문제의 핵심은 우선 List의 중복을 체크하는 것에 있다.
>>> 이후에 시간 복잡도를 개선해보자.
🤔 set을 사용할 수 없는 상황에서 List의 중복을 확인하는 방법은 무엇인가?
>>> dictionary를 사용해보자
✅ list1의 key, value로 등록한다.
✅ list2의 elemnt를 확인하면서 value값을 1씩 줄인다.
>>> dictionary의 모든 vlaue 합이 0이되면 두 리스트는 중복이다.
class Solution(object):
def is_distinct(self, list1, list2):
test = {}
for e in list1:
test[e] = 1 if e not in test else test[e] + 1
for e in list2:
if e not in test:
print(">>>")
print("it is distict plz add!", list1, list2)
print("<<<")
return True
test[e] -= 1
left = 0
for v in test.values():
left += v
print(">>>")
print("test: ", test)
print("<<<")
# left == 0 이면 distinct
return left != 0
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
result = []
n = len(nums)
test = 0
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
test += nums[i] + nums[j] + nums[k]
print("now: i, j, k", (i, j, k))
print("value: nums[i~k]", (nums[i], nums[j], nums[k]))
print("test: ", test)
if test == 0:
new_list = [nums[i], nums[j], nums[k]]
distinct = True
for res in result:
distinct = self.is_distinct(new_list, res)
print("distinct: ", distinct)
if not distinct:
break
if distinct:
result.append([nums[i], nums[j], nums[k]])
test = 0
return result
- 만들긴 했는데 코드가 너무 장황하다.
- 그리고 시간 복잡도가 O(n⁴)가 되어버렸다 ...
- 중복 체크에 O(n)이 추가됨
- 무조건 로직 잘못되었고 수정해야한다.
💀 추가로 distict로직이 잘못되었다.
def is_distinct(self, list1, list2):
print("test list1, list2", list1, list2)
test = {}
for e in list1:
test[e] = 1 if e not in test else test[e] + 1
print("set test", test)
for e in list2:
if e not in test:
return True
test[e] -= 1
print("updated test", test)
for v in test.values():
if v != 0:
return True
# v가 하나라도 0이 아니면 True
# 이후는 모두 False
return False
- 이렇게 변경되어야 한다.
- 전체 합이 아닌 하나라도 value가 0이 되는 순간 True가 되어야함
- {1: -1, 0: 1, 3: 0} 이면 left 합이 0이되어서 distinct인데도 False가 나옴
시간 복잡도를 줄여보자
예상대로 TimeLimit에러가 나왔다. 이제 어떻게 줄여야하는지 생각해보자.
✅ distict 판별은 무조건 O(n)이 걸린다.
>>> 새로운거랑 전체랑 비교해야 하므로
🤔 그럼 0이 되는 부분을 O(n²)이하로 만들 방법을 고안해야한다.
>>> 이건 불가능하다. O(n²)이 최선이다.
🤔 아니면 중복 여부를 O(1)로 만드는 방법이 없을까?
>>> 아래 찾았다.
순서쌍 찾기를 O(n²)으로 줄여보자
투포인터 사용하기
🗝️ 투포인터를 사용해보자
✅ 양쪽끝에 포인터를 둔다.
✅ 해당 포인터의 합을 계산한다.
✅ 나머지 중간 부분을 탐색하여 합이 0이 되는 부분을 찾는다.
>>> 여기서 O(n)이 소요된다.
✅ 포인터의 앞을 1증가 혹은 뒤를 1 감소시킨다.
>>> 각 경우의수에 대해 모두 계산해도 O(n)의 시간이다.
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
result = []
def find_zero(start, end):
print("test start", start, end)
if start >= end:
return
two_sum = nums[start] + nums[end]
for i in range(start + 1, end):
if two_sum + nums[i] == 0:
# duplicated check!
result.append((nums[start], nums[end], nums[i]))
break
find_zero(start + 1, end)
find_zero(start, end - 1)
find_zero(0, len(nums) - 1)
return result
- 아.. 이거 O(2ⁿ)이다.
- 2개씩 분기하기 때문에...
- 이게 아니라 하나씩 감소시키면 되잖아??
- ❌
✏️ 로직 수정하기
✅ start를 증가시키고 계산
✅ end를 감소 시키고 계산
🤔 근데 경우가 좀 많은 것 같은데
>>> start를 0~end - 1까지랑
>>> start고정 end -> start + 1까지
>>> start랑 end가 한칸씩 감소 ,
💀 이건 정렬되지 않은 배열에서 찾을때 발생하는 문제이다.
투 포인터의 핵심: 정렬을 이용하기
각 포인터의 모든 쌍을 찾는게 아니라, 투 포인터 자체가 많은 정보를 가질 수 있게 해야한다. 이때 정렬이 필수이다.
❌ 기존로직
[i, j, k, l, m, n, ... ,z]
>>> i <= j <= k ....
>>> start = i, end = z
>>> two_sum = i + z
>>> 이후 start + 1 ~ end - 1까지 돌려서 0되는 값을 찾는다.
>>> 이렇게 찾으면 비효율성 발생
✅ [i, j, k, l, m, n, ... ,z]
for i to z:
>>> i를 고정
>>> start = i + 1, end = z
✅ start + end를 계산해서 i와 합했을 때 0이 되어야 한다.
>>> if 3sum > 0: end 감소
>>> else: start 증가
✅ 만족하는 모든 순서쌍을 찾으면 된다.
>>> 한 방향 탐색이므로 O(n)이 됨.
투포인터 시도
class Solution(object):
def distinct(selt, list1, list2):
test = {}
for e1 in list1:
test[e1] = 1 if e1 not in test else test[e1] + 1
for e2 in list2:
if e2 not in test:
return True
test[e2] -= 1
for v in test.values():
if v != 0:
return True
return False
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
result = []
nums.sort()
for i in range(len(nums) - 1): #O(n)
acc = nums[i]
start = i + 1
end = len(nums) - 1
while start < end: #O(n)
tmp = acc
tmp += nums[start] + nums[end]
if tmp == 0:
test = [nums[i], nums[start], nums[end]]
is_distinct = True
for res in result:
is_distinct = self.distinct(res, test) #*O(n)
if not is_distinct:
break
if is_distinct:
result.append(test)
# what is next?
break
if tmp > 0:
end -= 1
else:
start += 1
return result
- 틀렸다
- 다음 경우에 오류
[-2, 1, 1, 0, 2]
>>> [-2, 0, 1, 1, 2]
# i = 0
nums[i] = -2
now start = 0, 2
tmp = -2 + 2 == 0
i = 0이 때 바로 i는 다음걸로 넘어간다.
>>> 실제로는 -2, 1, 1이 있음에도 계산이 안된다.
>>> 근데 이걸 고려하면 이전과 같이 똑같은 문제가 발생한다.
start와 end를 조절해서 새로운 조합을 구상해야함.
>>> case가 아닌 모든 경우에 대해서
>>> 예를들어 start를 1올리기, end를 1내리기 각각의 경우를 모두 고려
>>> 조합 증가로인해 시간복잡도가 다시 한번 증가한다.
❌❌❌ 결국에는 잘못된 로직
정답코드
GG
결국 구현에 어려움을 겪어서 gpt-o3 를 사용하여 답을 확인하기로 결정햇다. 더 이상 로직이 생각나지 않는다.
치명적인 문제를 발견했다.
✅ 중복체크를 상수배로 수정
>>> 내가 만든로직은 O(n)의 시간복잡도가 소요된다.
>>> 하지만, 논리를 잘 관찰하면 상수배로 체크가 가능하다.
✏️ 예시
[1, 2, -3, -3] ...
>>> i = 0이면 tmp = 1인 상태이다.
>>> 이때 start = 2 end = -1이다.
>>> 3sum = 0이 된다.
🤔 tmp = 0이지만 pointer를 다시 조정해야한다. 어디로 해야하는가?
>>> start와 end는 현재 값과 다른 곳으로 무조건 이동해야한다.
>>> ✏️ start를 2로 놓고 고정하면, end는항상 -3을 기대하게돈다
>>> 이거는 distict에 위배되니 항상 정답이 아니다.
>>> ✏️ 그렇다고 end를 -3으로 놓자니, start는 항상 2를 기대하게된다.
>>> 이것 역시 distict에 위배되어 항상 정답이 아니다.
>>> 🗝️ 고로 start와 end는 형재와 다른 값을 각각 가지도록 포인터를 이동시켜야한다.
>>> 이 부분을 놓친게 치명적이였다.
>>> 항상 result에는 다른 쌍이 들어갈 수 밖에없게된다.
>>> 내가 만든 distict체크 O(n)로직은 필요가 없어진다.
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
result = []
nums.sort()
for i in range(len(nums) - 1): #O(n)
if i > 0 and nums[i] == nums[i - 1]:
continue
acc = nums[i]
start = i + 1
end = len(nums) - 1
while start < end:
tmp = acc + nums[start] + nums[end]
if tmp > 0:
end -= 1
elif tmp < 0:
start += 1
else:
result.append((nums[i], nums[start], nums[end]))
while start < end and nums[start] == nums[start + 1]:
start += 1
while start < end and nums[end] == nums[end - 1]:
end -= 1
start += 1
end -= 1
return result
- 정답이다
- t: O(n²) 80.64% Beats
- append 이후 로직이 끝가지 헷갈렸다.
✅ while문은 각 start와 end가 달라지기 직전가지만 이동한다.
✅ 각자 달라지기 직전까지 이동했으니 +1 -1을 하여 포인터를 움직이면 중복되지 않는 새로운 쌍이 나온다.