Two Pointer

• 주로 선형 데이터 구조에서 두 개의 인덱스를 관리하여 특정 조건을 만족하는
  부분 집합이나 특정 값을 찾는 알고리즘.

방법은 아래와 같음!

1. 두 포인터(인덱스)를 시작점으로 초기화.
2. 규칙에 따라 포인터 이동

• 같은 배열에서 동일 방향으로 이동,
• 같은 배열에서 마주보는 방향으로 이동,
• 서로 다른 배열에서 이동 등
• 여러 형태에서 효율적인 시간복잡도를 가짐.

3. 두 포인터 중 하나 혹은 둘 모두 끝에 도달할 때까지 반복.

예제로 알아보자!

🦕 [2003] 수들의 합2

위 문제를 보고 가장 먼저 떠올릴 수 있는 방법은 Brute Force임.

하지만 아래의 두 경우는 시간초과를 받을 수 있음.

1. Brute Force를 이용한 방법

• 시간복잡도 - O(N3)

int ans = 0;
		for (int i = 0; i < N; i++) {
				for (int j = i: j <N; j++) {
						int sum = 0;
						for (int k = i; k <= j; k++)
								sum += arr[j];
						if (sum == M) ans++;
						else if (sum > M) break;
		}
}

• 시간복잡도 - O(N2)

int ans = 0;
		for (int i = 0; i < N; i++) {
				int sum = 0;
				for (int j= i:j < N; j+) {
						sum += arr ［j］；
						if (sum == M) ans++;
						if (sum >= M) break;
		}
}

문제에서는 자연수 수열이므로, 각 시작점 i에 대해 [ i : j ]가 M이 될 수 있는지
Binary Search + 누적합으로도 해결할 수 있음.

2. Binary Search + 누적합을 이용한 방법

• 시간복잡도 O(N * logN)

// 미리 누적합을 구한 후
long[] acc = new long[N + 1];
for (int i = 1; i < N; i++)
		acc[i] = acc[i - 1] + arr[i];

// 이분탐색을 이용.
int ans = 0;
for (int i = 1; i < N; i++) {
		int l = i, r = N;
		while (l < r) {
				int m = (l+ r) / 2;
				long sum = acc[m] - acc[i - 1];
				if (sum > M)r = m - 1;
				else if (sum < M) l = m + 1;
				else {
						ans++;
					  break;
				}
		}
}

단 음수를 포함한 정수 수열일 경우 위 방법은 통하지 않음.

3. Two Pointer를 이용한 방법

위 방법도 가능하지만 이제 Two Pointer를 이용한 방법을 보여주도록 하겠음.

---

[ i : j ] 의 j가 늘어나면 구간의 합이 증가한다는 특성을 이용해 [ i : j ] == M을 만족하는 구간을
Two Pointer로 찾아보는 것임.

만약 두 인덱스를 7과 8이라고 가정해보자.
[ i : j ]의 연속합 ⇒ $a_7$ + $a_8$ = 4 이므로 원하는 값인 5에 만족하지 못함.
이때 i는 고정한 후, j를 오른쪽으로 이동하여 포함하는 범위를 늘림.

[ i : j ]의 연속합 ⇒ $a_7$ + $a_8$ + $a_9$ = 5 으로 값은 만족하며,
i = 7 인 구간의 유일한 답이 됨.
j가 증가하면 합이 늘어나므로 더 이상 확인할 필요가 없음.

이후 i = 8 인 경우를 조사할 때, Two Pointer는 아래와 같은 방법을 사용.
i = 7에 대해 [ 7 : 7 ], [ 7 : 8 ] 이 원하는 값(5) 보다 작았음을 이용하여,
i = 8일때 역시 [ 8 : 9 ] 부터 조사를 시작할 수 있음.
([ 8 : 8 ] 구간을 건너 뜀.)

Two Pointer에서 중요한 것은 이전 탐색 포인터를 재사용하는 것!

Two Pointer를 이용한 풀이

• 시간복잡도 O(N)

  i가 0부터 N - 1까지 움직이는 동안 rightIndex의 총 움직임이 N이므로
  전체 시간복잡도는 O(N)이 나온다.

  ---

1. 현재 구간의 합이 M보다 크거나 같을 때까지 j를 이동.
2. 합이 M이라면 ans 증가.
3. 이후 i를 이동하므로 현재 구간의 합에서 A[ i ]를 제함.

int rightIndex = 0;
int currentSum = arr [0];
		for (int i = 0; i < N; i++) {
				while (currentSum < M && rightIndex < N - 1)
						currentSum += arr[++rightIndex];
				if (currentSum == M) ans++;
				currentSum -= arr[i];
}

🦕 [2470] 두 용액

https://www.acmicpc.net/problem/2470

이 문제는 BinarySearch로 해결했지만, Two Pointer를 이용해서도 풀 수 있음.

각 i에 대해 j를 이동하면서 최적의 쌍이 되는 값을 찾는데 이때,
i, j 의 이동 방향은 마주보는 방향이 됨.

• $a_i$ + $a_j$ 의 합이 음수라면 j는 작아지는 방향으로만 움직이므로, i를 움직임. (j를 움직이면 음수인 값이 더 작아지기 때문)
  
• $a_i$ + $a_j$ 의 합이 양수라면 현재 $a_j$ 보다 작은 값과 혼합해보는 것이 현재의 최적 값보다 0에 가까울 수 있음.
  → j를 작아지게 하는 방향으로 이동.

해당 문제는 서로 다른 두 용액을 혼합하는 문제이므로, i == j 가 되면 중단.

• 시간복잡도 O(N)

1. leftIndex를 고정하여 검사하는 방법

int rightIndex = N - 1;
for (int i = 0; i < rightIndex; i++) {
		int currentSum = arr[i] + arr[rightIndex];
		int currentAbs = Math.abs(currentSum);
		if (ansAbs › currentAbs) {
				ansAbs = currentAbs;
				ansLeftIndex = i;
				ansRightIndex = rightIndex;
		}
		while (currentSum > 0 && i < rightIndex - 1) {
				currentSum = arr[i] + arr[--rightIndex];
				currentAbs = Math.abs(currentSum);
				if (ansAbs > currentAbs) {
						ansAbs = currentAbs;
						ansLeftIndex = i;
						ansRightIndex = rightIndex;
				}
		}
}

2. leftIndex, rightIndex를 모두 움직이는 방법

int leftIndex = 0;
int rightIndex = N - 1;
		while (leftIndex ‹ rightIndex) {
				int currentSum = arr[leftIndex] + arr[rightIndex];
				int currentAbs = Math.abs(currentSum);
				if (ansAbs > currentAbs) {
						ansAbs = currentAbs;
						ansLeftIndex = leftIndex;
						ansRightIndex = rightIndex;
		}
		if (currentSum > 0) rightIndex--;
		else leftIndex++;
}

🦕 [2003] 수들의 합2

https://www.acmicpc.net/problem/2003

• 시간복잡도 - O(N)

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int ans = 0;

        int rightIndex = 0;
        int currentSum = arr[0];
        // 하나의 포인터는 고정 사용
        for (int i= 0; i < N; i ++) {
            while(currentSum < M && rightIndex < N - 1)
                currentSum += arr[++rightIndex];
            if (currentSum == M) ans++;
            currentSum -= arr[i];
        }
        System.out.println(ans);
    }
}

만약 두 포인터를 모두 움직이고 싶다면.

int left = 0, right = 0, sum = 0;

while (true) {
    if (sum >= M) {
        sum -= arr[left++];
    } else if (right == N) {
        break;
    } else {
        sum += arr[right++];
    }

    if (sum == M) {
        ans++;
    }
}