투 포인터 알고리즘 - 다른 방향
배열에서 두 원소의 합이 어떠한 값 X와 일치하는 경우의 수를 구할 때 사용하는 알고리즘
단, 다른 방향 진행 방법에서는 배열이 정렬된 상태에서 가능하다.
배열이 2개가 존재할 때, 배열 하나는 포인터가 왼쪽에서부터 시작하여 오른쪽으로 이동하고
다른 하나는 포인터가 오른쪽에서부터 시작하여 왼쪽으로 이동한다.
배열을 1개 사용할 때, start 포인터가 왼쪽에서 하나씩 증가하고 end 포인터가 오른쪽에서 하나씩 감소했던 것과 동일한 방식이다.
사실 배열이 한 개든, 두 개든 알고리즘 자체는 동일한데, 그냥 분리해서 이해하고자 따로 다뤘다.
투 포인터 알고리즘 - 2. 다른 방향(배열 1개)
투 포인터 알고리즘 - 다른 방향 배열에서 두 원소의 합이 어떠한 값 X와 일치하는 경우의 수를 구할 때 사용하는 알고리즘 단, 다른 방향 진행 방법에서는 배열이 정렬된 상태에서 가능하다. 같
lotuslee.tistory.com
[예제]
배열 a가 -1 1 1 1 4 5 7 의 요소를 가지고 있고, 배열 b가 -3 0 3 6 8 9 12 의 요소를 가지고 있을 때,
두 배열의 요소를 더해서 합이 X = 10 이 되는 모든 경우의 수를 하여라.
배열 a를 이동하는 포인터를 pa, 배열 b를 이동하는 포인터를 pb 라고 하면
pa와 pb의 초기값은 pa = 0, pb = 6 이다.
pa 포인터는 왼쪽부터 시작하여 오른쪽으로 이동하고, pb 포인터는 오른쪽에서 시작해 왼쪽으로 이동하기 때문이다.
pa = 0, pb = 6, sum = 12, cnt = 0
sum = a[pa] + b[pb] = a[0] + b[6] = 11 이다.
X(10) < 11 이므로 sum은 기존의 11보다 더 작아야 한다.
그러므로 pb를 왼쪽으로 하나 이동하여서 12보다 더 작은 값을 가리키도록 한다.
pa = 0, pb = 5, sum = 8, cnt = 0
sum = a[pa] + b[pb] = a[0] + b[5] = 8 이다.
X(10) > 8 이므로 sum은 8보다 더 커야 한다.
그러므로 pa를 오른쪽으로 하나 이동하여서 -1보다 더 큰 값을 가리키도록 한다.
pa = 1, pb = 5, sum = 10, cnt = 3
sum = a[pa] + b[pb] = a[1] + b[5] = 10 이다.
X(10) = 10 이 되어 X와 동일하다. a[1]보다 오른쪽의 요소들 중 a[1]와 같은 값이 연속하여 존재하는지 카운트한다.
a[1] = a[2] = a[3] = 1 이므로 aCnt = 3이고, pa는 계속 이동하다가 pa = 4가 될 때 이동을 멈춘다.
pb의 경우도 마찬가지다. 연속하는 9는 b[5]로 1개이다. 그러므로 bCnt = 1이 된다.
cnt += aCnt * bCnt 를 하면 cnt = 3이 된다.
pa = 4, pb = 4, sum = 12, cnt = 3
sum = a[pa] + b[pb] = a[4] + b[4] = 12 이다.
X(10) < 12 이므로 sum은 12보다 더 작아야 한다.
그러므로 pb를 왼쪽으로 하나 이동하여서 8보다 더 작은 값을 가리키도록 한다.
pa = 4, pb = 3, sum = 10, cnt = 4
sum = a[pa] + b[pb] = a[4] + b[3] = 10 이다.
X(10) = 10 이 되어 X와 동일하다. a[4]보다 오른쪽의 요소들 중 a[4]와 같은 값이 연속하여 존재하는지 카운트한다.
a[4]가 유일하므로 aCnt = 1이고, pa = 5로 이동한다.
b[3]보다 왼쪽의 요소들 중 b[4]와 같은 값이 연속하여 존재하는지 카운트한다. b[3]이 유일하므로 bCnt = 1 이다.
cnt += aCnt * bCnt = 4
pa = 5, pb = 2, sum = 8, cnt = 4
sum = a[pa] + b[pb] = a[5] + b[2] = 8 이다.
X(10) > 8 이므로 sum은 8보다 더 커야 한다.
그러므로 pa를 오른쪽으로 하나 이동하여서 5보다 큰 값을 가리키도록 한다.
pa = 6, pb = 2, sum = 10, cnt = 5
sum = a[pa] + b[pb] = a[6] + b[2] = 10 이다.
X(10) = 10 이 되어 X와 동일하다. a[6]보다 오른쪽의 요소들 중 a[6]와 같은 값이 연속하여 존재하는지 카운트한다.
a[6]가 유일하므로 aCnt = 1이다. pa = 7로 이동한다.
b[2]보다 왼쪽의 요소들 중 b[2]와 같은 값이 연속하여 존재하는지 카운트한다. b[2]이 유일하므로 bCnt = 1 이다.
cnt += aCnt * bCnt = 1
pa가 a의 범위를 벗어났으므로 반복문을 종료한다.
배열 a의 요소와 배열 b의 요소를 더해서 합이 X = 10이 되는 경우의 수는 5개이다.
소스코드 :
public static long getCount() {
long count = 0;
int pa = 0, pb = b.length - 1;
while (pa < a.length && pb >= 0) {
long sum = a[pa] + b[pb];
if (sum == 0) {
int n = a[pa];
int m = b[pb];
long aCnt = 0, bCnt = 0;
while (pa < a.length && a[pa] == n) {
pa++;
aCnt++;
}
while (pb >= 0 && b[pb] == m) {
pb--;
bCnt++;
}
count += aCnt * bCnt;
}
else if (sum > 0 || pa == a.length - 1)
pb--;
else if (sum < 0 || pb == 0)
pa++;
}
return count;
}
'Algorithm & DS > 투 포인터' 카테고리의 다른 글
| 투 포인터 알고리즘 - 2. 다른 방향(배열 1개) (2) | 2021.02.16 |
|---|---|
| 투 포인터 알고리즘 - 1. 같은 방향 (0) | 2021.02.15 |