알고리즘 - 투 포인터(two pointer)

이미 정렬이 완료된 배열 or 리스트에서 두 개의 인덱스(포인터)를 이용해

 

포인터에 담긴 값과 원하는 결과를 비교해 원하는 해를 구하는 알고리즘.

 

이중 반복문으로도 해결가능한 문제이나 O(N^2) 의 시간이 소요.

 

정렬이 안된 배열에서도 O(NlogN), 정렬된 배열에선 O(N)의 시간으로 단축됨.

 

ex)

배열 내 합이 S가 되는 순서쌍 찾기.

 

배열의 앞 뒤에서 포인터로 좁혀오며 순서쌍을 찾찾.

 

투 포인터(앞 : l  뒤 : r)가 지시하는 두 요소의 합을 S 와 비교

 

l<=r 을 만족하는 동안

 

합보다 S가 작으면 r 을 한칸 앞.

 

합보다 S가 크면  l을 한칸 뒤.

 

합과 같으면 r 을 한칸 앞, l 을 한칸 뒤.  

 

조건이 깨지면 알고리즘 끝.