투 포인터 알고리즘 - 2. 다른 방향(배열 1개)

투 포인터 알고리즘 - 다른 방향

배열에서 두 원소의 합이 어떠한 값 X와 일치하는 경우의 수를 구할 때 사용하는 알고리즘
단, 다른 방향 진행 방법에서는 배열이 정렬된 상태에서 가능하다.

같은 방향으로 진행되는 투 포인터 알고리즘은 다른 포스팅에서 참고하면 된다.
투 포인터 알고리즘 - 같은 방향

투 포인터 알고리즘 - 1. 같은 방향

다른 방향으로 진행하는 알고리즘은, 1. 하나의 배열을 사용하는 방법과 2. 두 개의 배열을 사용하는 방법이 있다.
반복문 탈출조건이 약간 다르긴 한데 알고리즘은 동일하다.

필요한 변수

- 배열의 0번째부터 시작하여 하나씩 증가하는 start 포인터
- 배열의 마지막부터 시작하여 하나씩 감소하는 end 포인터
- arr[start]와 arr[end]의 합을 저장하는 sum 변수

같은 방향 진행 방법과 다른점은 같은 방향 진행 방법에서는 start 포인터와 end 포인터 모두 0인덱스에서 시작하여 점점 증가하였는데, 다른 방향 진행 방법에서는 두 포인터가 양끝에서 시작해서 점점 가까워지는 방향으로 진행된다.

알고리즘 :

1. sum = X 이면,
arr[start]와 동일한 연속하는 값의 개수를 카운트(cnt1), arr[end]와 동일한 연속하는 값의 개수를 카운트(cnt2)
그리고 이 둘을 곱하여 최종 cnt에 더한다.
cnt += cnt1*cnt2

2. sum > X 이면, end 포인터를 감소시킴

3. sum < X 이면, start 포인터를 증가시킴

4. 하나의 배열을 사용하는 경우 start<end 을 만족할 때까지 위 과정을 반복한다.
두 개의 배열을 사용하는 경우 start<arr1.length && end>=0 을 만족할 때까지 위 과정을 반복한다.



[예제]
먼저 하나의 배열만 사용하는 경우를 보자.
X = 5이고, 배열 arr은 차례대로 -1 0 2 2 3 4 5 5 라고 하자. 여기서 배열 arr은 정렬된 상태여야 한다.
맨 처음 start 포인터는 0을 가리키고 있고, end 포인터는 마지막 인덱스인 7을 가리키고 있다.
start = 0, end = 7, sum = 4, cnt = 0

arr[start] + arr[end] = sum 이 X=5 와 같은지 비교해봤더니 -1 + 5 = 4 로 X보다 작다.
sum < X 일 때는 sum이 더 증가해야 하므로 start 포인터를 증가시킨다.(오름차순으로 정렬되어 있으므로 arr[start]보다 arr[start+1]의 값이 더 크기 때문에 arr[start+1] + arr[end]이arr[start] + arr[end]보다 더 클 것을 기대할 수 있다.)
start = 1, end = 7, sum = 5, cnt = 0

이번에는 arr[1] + arr[6] = 1 + 4 = 5로 X와 일치한다.
start 위치부터 시작하여 연속으로 등장하는 0의 개수가 몇 개인지 확인한다.
여기서는 arr[2] = 2 이므로 연속으로 등장하는 0는 arr[1]이 유일하다. 그러므로 개수는 1개이다. -> cnt1 = 1
start가 가리키는 곳은 그 다음인 2가 된다.

end 위치에서부터 연속으로 등장하는 5의 개수가 몇 개인지 확인한다.
연속으로 등장하는 5의 개수는 arr[6] = arr[7] = 5 이므로 2개이다. -> cnt2 = 2
end 포인터는 제일 처음 5가 등장하는 arr[6] 바로 이전인 5 인덱스를 가리키게 된다.

그리고 cnt 에 cnt1 * cnt2 를 더한다.

start = 2, end = 5, sum = 6, cnt = 2

sum = arr[2] + arr[5] = 6 이므로 sum>X 이다.
sum이 X보다 크므로 sum을 감소시킬 필요가 있다. 그러므로 end 포인터를 하나 감소시킨다.
start = 2, end = 4, sum = 5, cnt = 2

sum = 5 이므로 X와 일치한다.
start 위치부터 시작하여 2의 개수는 arr[2] = arr[3] = 2로 2개이다. -> cnt1 = 2
start 포인터는 그 다음인 4로 이동한다.
end 위치부터 시작하여 3의 개수는 arr[4] 하나뿐이므로 cnt2 = 1
end 포인터는 그 이전인 3으로 이동한다.

cnt에는 cnt1 * cnt2를 더해준다.

start = 4, end = 3, sum = 5, cnt = 4

start포인터와 end 포인터가 교차되었다.
start > end 이므로 반복문을 종료하고 빠져나온다.

최종적으로 합이 5가 되는 경우의 수는 4가지가 된다.

배열 2개를 이용하는 경우도 이와 탈출조건만 다를 뿐 동일하다.

소스 코드 :

	public static long getCount(int X) {

		long count = 0;
		int s = 0, e = arr.length - 1;

		while (s < e) {

			long sum = arr[s] + arr[e];

			if (sum == X) {
				int a = arr[s];
				int b = arr[e];
				long acnt = 0, bcnt = 0;

				while (s < arr.length && arr[s] == a) {
					s++;
					acnt++;
				}
				while (e >= 0 && arr[e] == b) {
					e--;
					bcnt++;
				}
				count += acnt * bcnt;
			}

			else if (sum > X)
				e--;

			else if (sum < X)
				s++;
		}

		return count;

	}