배열 중 합이 0이되는 엘리먼트를 출력하는 문제이다.
이 문제를 보고 떠올린 것은 다중for문으로 모든경우를 돌아 프로트포스로 푸는 방법 밖에 없었다.
그런데 투 포인터를 이용한 방법이란 것도 존재했다.
두 개의 포인터를 두고 포인터를 옮겨가며 리스트를 순회하는 방법이다. 주로 정렬이 되 있을 경우 순차적으로 원하는 값에 가까워지게 조작할 수 있다.
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
result=[]
for i in range(len(nums)-2):
if i>0 and nums[i]==nums[i-1]:
continue
left,right=i+1,len(nums)-1
while left<right:
sum=nums[i]+nums[left]+nums[right]
if sum<0 :
left+=1
elif sum>0:
right-=1
else:
result.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 result
이 투 포인터 방식을 사용할 수 있는 다른 문제가 있다.
배열에 따라 고일 수 있는 물의 크기를 계산하는 문제이다.
def trap(self, height: List[int]) -> int:
if not height:
return 0
volume = 0
left, right = 0, len(height) - 1 # 포인터
left_max, right_max = height[left], right[max] # 포인터 높이 초깃값
while left < right:
left_max, right_max = max(height[left], left_max), max(height[right], right_max)
# 우측으로 이동
if left_max <= right_max:
volume += left_max - height[left] left += 1
# 좌측으로 이동
else:
volume += right_max - height[right] right -= 1
return volume좌우 맨 끝을 두 개의 포인터로 잡고 현재상태에서 가장 높은 높이를 갱신해나가며 리스트를 순회하는 방법이다.
배열,리스트를 순회할 때 효율성을 높여야할 필요가 있다면 고려할 방법으로 기억해놓아야겠다.
+참고: 책 파이썬 알고리즘 인터뷰(박상길)
