Two-Pointer(투포인터)

정렬된 리스트에서 두 포인터를 이용해 순차적으로 접근하면서 원하는 문제의 해를 검색할 때 사용하는 기법

한 원소를 선택하고 나머지 원소를 탐색하고, 또 다른 원소를 선택하고 나머지 원소를 탐색하는 O(n^2)의 방법과는 달리 투 포인터를 사용하면 O(n)로 끝낼 수 있다.

포인터의 배치

1. 배열의 첫번째 원소와 배열의 마지막 원소에서 시작하는 경우(반대 진행 방향)
2. 두 포인터 모두 첫번째 원소에서 시작하는 경우(같은 진행 방향)

반대 진행 방향

n개의 정수를 가진 정렬된 배열 A가 있을 때 두 원소의 합이 X인 경우가 있는지에 대해 생각해보자.

하나의 포인터는 첫번째 원소를 나타내고 다른 하나는 마지막 원소를 나타낸다.
두 포인터는 서로를 향한 방향으로 이동하는데 두 포인터가 만나거나 어떤 조건을 만족할 때까지 이동한다.

1. 두 원소의 합이 x보다 작다면 왼쪽 포인터를 오른쪽으로 이동한다.

   • 정렬된 배열에서 합을 키우기 위해 오른쪽으로 이동

2. 만일 두 원소의 합이 x보다 크다면 오른쪽 포인터를 왼쪽으로 이동한다

   • 정렬된 배열에서 합을 줄이기 위해 왼쪽으로 이동

3. 두 수의 합이 x인 경우를 찾을 때까지 반복한다

int arr[10];

bool twoPointer(int len, int x) {
	int left = 0;
	int right = len - 1;
	while (left < right) {
		if (arr[left] + arr[right] == x)
			return true;
		else if (arr[left] + arr[right] > x)
			right--;
		else
			left++;
	}
	return false;
}

같은 진행 방향

n개의 정수를 가진 배열 A가 있을 때, 배열에서 i,j까지 원소의 연속된 합이 x가 되는 경우가 있는지에 대해 생각해보자.

두 포인터를 start, end라고 지칭할 때, start = 0, end = 0으로 시작한다.

이 때 포인터는 항상 start <= end여야 한다.

1. 현재 부분합이 m 초과이거나, end == n이면 start 증가
2. 부분 합이 m 이하라면 end 감소
3. 현재 부분합이 m이라면 (결과 + 1)
4. start < n 까지 반복한다.

int twoPointer(int n, int x){
    long sum = 0;
    int start = 0;
    int end = 0;
    int result = 0;
    while (start < n) {
        if (sum > m || end == n)	sum -= arr[start++];
        else 	sum += arr[end++];
	
	if (sum == m)	result++;
    
    return result;
}

응용

• Sliding Window
  투 포인터와 유사하게 접근하되 투 포인터처럼 범위의 크기가 줄었다 늘었다 하는 것이 아니라 일정한 크기를 유지하면서 이동