투 포인터는 이름 그대로 두 개의 포인터를 사용하여 배열에서 원하는 결과를 얻는 방법이다.
다중 반복문이 사용되어야 하는 경우에서 해당 방법론을 사용할 수 있다면 좀 더 효율적으로 문제를 풀 수 있다.
포인터의 배치 위치는 일반적으로 아래와 같다.
동일한 방향에서 시작하는 경우, 첫 번째 원소에 둘 다 배치
서로 다른 방향에서 시작하는 경우, 첫 번째 원소와 마지막 원소에 배치
투 포인터의 활용
투 포인터는 배열에서 여러번의 다중 반복문이 사용되어야 할 경우에 효율적이다.
예시로는 구간합 찾기 문제가 있다.
아래와 같은 배열에서 구간합이 9인 구간을 찾아주세요
1 2 5 3 7 2 4 3 2
해당 문제를 나이브하게 다중 루프를 사용할 경우 시작 구간 i와 구간합을 계산하기 위해 i + 1부터 시작하는 j를 사용하여 2개의 for loop을 이용해 해결할 수 있다.
하지만 투 포인터 방법을 활용하면 아래와 같이 해결할 수 있다.
두 포인터 start와 end를 첫번째 원소를 가리키도록 한다. 지금 sum은 1로 우리가 원하는 구간합인 9보다 작다. 따라서 다른 원소를 합칠 수 있으며 end를 한 칸 뒤로 가도록 할 수 있을 것이다.
이후에 2를 더한다 sum은 3이 되며 아직 9보다 작으므로 end를 한 칸 더 뒤로 보낸다. 이후 5를 더하고도 8이 되기 때문에 end가 한 칸 더 밀려 3을 가리키게 된다.
3을 더하게 되면 sum이 11로 우리가 찾고 있던 9보다 크다. 따라서 원소를 빼야 한다. start를 한 칸 올리면서 원래 start가 가리키고 있던 값을 빼면 될 듯 하다.
start는 2를 가리키게 된다. sum = 10으로 아직 우리가 찾던 9보다 큰 수이다. 따라서 현재 start가 가리키고 있는 2를 sum에서 빼게 되며 start는 한 칸 앞으로 이동한다.
이제 sum이 9보다 작으므로 end가 움직일 차례이다. 그 이후에는 sum이 15가 되므로 start가 움직이며 sum은 10이 된다.
그 다음도 9보다 크므로 3을 빼게 되며 start와 end 모두 7을 가리키게 된다.
이후 7이 9보다 작으므로 end가 2를 가리키며 sum은 9가 된다.
이제 우리가 찾는 값이 되었으므로 해당 구간을 답으로 출력하면 된다.
// 알고리즘 - 투 포인터
// for-loop vs two pointers
import java.util.Arrays;
public class Main {
public static int[] twoPointers(int[] arr, int target) {
int start = 0;
int end = 0;
int sum = 0;
int[] result = {-1, -1};
while(true){
if (sum > target){
sum -= arr[start++];
} else if (end == arr.length){
break;
} else{
sum += arr[end++];
}
if (sum == target){
result[0] = start;
result[1] = end - 1;
break;
}
}
return result;
}
public static void main(String[] args) {
int[] arr = {1, 2, 5, 3, 7, 2, 4, 3, 2};
System.out.println(Arrays.toString(twoPointers(arr, 9)));
System.out.println(Arrays.toString(twoPointers(arr, 14)));
}
}
이분 탐색과도 꽤 비슷한 시나리오로 흘러간다. 차이점은 이분 탐색은 중간값을 사용하여 start와 end를 수정해가는데 비해 투 포인터 알고리즘은 각각의 포인터를 직접 움직인다는 것이다.
