[알고리즘] 투 포인터

Two Pointer

배열이나 리스트와 같은 1차원 자료구조에서 두 개의 포인터를 이용하여 문제를 보다 효율적으로 해결하는 방법이다.
주로 정렬된 배열에서 특정한 조건을 만족하는 부분 배열이나 쌍을 찾는 데 사용이 된다.

배열의 시작과 끝, 또는 다른 두 위치에 포인터를 두고 특정한 조건을 만족할 때까지 포인터를 이동시켜 문제를 해결한다.

🤔 언제 사용을 할까?

* 정렬된 배열에서 특정한 조건을 만족하는 부분이나 배열이나 쌍을 찾을 때

예를 들어서 정렬된 배열에서 두 수의 합이 특정한 값이 되는 경우를 찾을때 사용이 가능하다.

* 문자열이나 배열에서 특정 패턴을 찾을 때

팰린드럼 여부를 검사하거나, 중복된 원소를 제거할 때

동작 과정

2	5	1	5	8	2	3	4	1	1

이렇게 1차원의 자료구조가 있다고 하자, 해당 원소의 부분합이 특정 조건 값인 M 경우를 찾는 동작을 간단하게 알아보자

처음에는 두 포인터 start, end 인덱스는 0으로 시작한다. 그리고 항상 start <= end를 만족을 해야한다.
2개의 포이터는 현재 부분 배열의 시작과 끝을 의미한다.

• 현재 부분 배열의 합이 M보다 작을 경우, end포인터를 한 칸 늘린다.
• 현재 부분 배열의 합이 M보다 클 경우, 두 포인터을start포인터를 다음칸으로 옮긴다.
• 현재의 부분 배열의 합이 M과 동일할 경우, 결과값 +1

$M=13$일 경우를 알아보자

2	5	1	5	8	2	3	4	1	1	M
start, end

초기에는 start와 end는 처음 요소에 위치한다.
초기 상태에서 요소의 합은 5이므로 end를 한 칸 뒤로 이동

2	5	1	5	8	2	3	4	1	1	M
start	end

$M = 7$이므로, 뒤로 이동

2	5	1	5	8	2	3	4	1	1	M
start		end

2	5	1	5	8	2	3	4	1	1	M
start			end

$M=13$이므로 연속적인 요소의 합이 조건에 맞는 경우를 하나 찾았다.

또 다른 경우를 찾기 위해서 start를 뒤로 이동한다.

2	5	1	5	8	2	3	4	1	1	M
	start		end

이렇게 동작을 하면서 조건에 맞는 경우를 찾는다.

만약 부분 합이 조건에 초과를 했을 경우는

2	5	1	5	8	2	3	4	1	1	M
		start		end

이 경우에는 부분 합이 15다.
그렇기에 바로 start를 이동시킨다.