투포인터(Two Pointers) 알고리즘

개념

투포인터 알고리즘은 리스트에서 순차적으로 접근해야 할 때 두 개의 위치(인덱스)를 기록하면서 처리하는 알고리즘이다. 정렬되어 있는 두 리스트의 합집합에도 사용된다.

두 개의 인덱스 중 하나는 탐색을 할 때마다 반드시 1 증가한다. 어느 인덱스라도 리스트의 크기에 도달해야 하므로 투포인터 알고리즘의 시간복잡도는 O(N)이 된다.

 

설명

개요

1. 부분합이 찾는 값이거나 오른쪽 인덱스가 (리스트의 크기 - 1)이라면 왼쪽 인덱스를 1 증가시킨다.

2. 부분합이 찾는 값이 아니라면 오른쪽 인덱스를 1 증가시킨다.

3. 위 과정을 왼쪽 인덱스가 (리스트의 크기 - 1)이 될 때까지 반복한다.

 

구현

구간이 연속적일 때

0	1	2	3	4	5
1	4	2	2	1	2

어떤 숫자들의 리스트가 위와 같이 주어질 때, 해당 리스트의 부분 연속 수열의 합이 '5'를 몇 번 가지는 지 확인하는 문제를 풀어보자.

 

• [0, 0] 일 때(answer : 0)

0	1	2	3	4	5
1	4	2	2	1	2

처음에는 왼쪽 인덱스와 오른쪽 인덱스가 0을 가리키도록 한다. 현재의 부분합은 1이다. 1 < 5 이므로 오른쪽 인덱스를 1 증가시킨다.

 

• [0, 1]일 때(answer : 0)

0	1	2	3	4	5
1	4	2	2	1	2

현재 범위의 부분합은 5이다. 원하는 값을 찾았으므로 answer를 1 증가시키고, 왼쪽 인덱스를 1 증가시킨다. 

 

• [1, 1]일 때(answer : 1)

0	1	2	3	4	5
1	4	2	2	1	2

현재 범위의 부분합은 4이다. 4 < 5이므로 오른쪽 인덱스를 1 증가시킨다.

 

• [1, 2]일 때(answer : 1)

0	1	2	3	4	5
1	4	2	2	1	2

현재 범위의 부분합은 6이다. 6 > 5 이므로 왼쪽 인덱스를 1 증가시킨다.

 

• [2, 2]일 때(answer : 1)

0	1	2	3	4	5
1	4	2	2	1	2

현재 범위의 부분합은 2이다. 2 < 5 이므로 오른쪽 인덱스를 1 증가시킨다.

 

• [2, 3]일 때(answer : 1)

0	1	2	3	4	5
1	4	2	2	1	2

현재 범위의 부분합은 4이다. 4 < 5 이므로 오른쪽 인덱스를 1 증가시킨다.

 

• [2, 4]일 때(answer : 1)

0	1	2	3	4	5
1	4	2	2	1	2

현재 범위의 부분합은 5이다. 원하는 값을 찾았으므로 answer를 1 증가시키고, 왼쪽 인덱스를 1 증가시킨다.

 

• [3, 4]일 때(answer : 2)

0	1	2	3	4	5
1	4	2	2	1	2

현재 범위의 부분합은 3이다. 3 < 5 이므로 오른쪽 인덱스를 1 증가시킨다.

 

• [3, 5]일 때(answer : 2)

0	1	2	3	4	5
1	4	2	2	1	2

현재 범위의 부분합은 5이다. 원하는 값을 찾았으므로 answer를 1 증가시킨다. 오른쪽 인덱스를 1 증가시켜야 하는데 범위를 벗어나므로 왼쪽 인덱스만 1 증가시킨다.

 

• [4, 5]일 때(answer : 3)

0	1	2	3	4	5
1	4	2	2	1	2

현재 범위의 부분합은 3이므로 왼쪽 인덱스를 1 증가시킨다.

 

• [5, 5]일 때(answer : 3)

0	1	2	3	4	5
1	4	2	2	1	2

현재 범위의 부분합은 2이므로 왼쪽 인덱스를 1 증가시킨다. 이때 왼쪽 인덱스가 마지막 인덱스이므로 탐색을 종료한다.

public class TwoPointers {

	public static void main(String[] args) {
		int[] arr = {1, 4, 2, 2, 1 ,2};
		int answer = 0;
		int target = 5;
		int len = arr.length;
		
		int sum = 0; //구간의 합
		int left = 0;
		int right = 0;
		while(left < len) {
			if(sum == target) { //부분합이 찾는 값과 같다면
				answer ++; //카운트 1 증가하고
				left ++; //왼쪽 범위를 줄여주고
				sum -= arr[left - 1]; //이전 인덱스의 값을 빼준다
			}//부분합이 찾는 값보다 크거나 오른쪽 인덱스가 이미 범위 밖이라면 
			else if(sum > target || right >= len) { 
				left ++; //왼쪽 범위를 줄여주고 
				sum -= arr[left - 1]; //이전 인덱스의 값을 빼준다
			}else if(sum < target) { //부분합이 찾는 값보다 작다면 
				right ++; //오른쪽 범위를 줄여주고 
				sum += arr[right - 1]; //이전 인덱스의 값을 빼준다
			}
		}
		
		System.out.print(answer);
	}

}

 

구간이 연속적이지 않을 때

그렇다면 무작위로 두 개의 데이터를 골라 찾는 값인지 확인하는 문제는 어떻게 풀어야 할까? 바로 연속성을 만들어주는 것이다.

연속성을 만들어주는 방법은 아래 두 가지 방법이 있다.

1. 데이터 정렬(Arrays.sort(arr))

2. 오른쪽 인덱스를 처음(0)에서 시작하는 것이 아니라 마지막(arr.length - 1)에서 시작

public class TwoPointers {

	public static void main(String[] args) {
		int[] arr = {1, 4, 2, 2, 1 ,2};
		int answer = 0;
		int target = 5;
		int len = arr.length;
        
		Arrays.sort(arr); //데이터 정렬 
		
		int left = 0;
		int right = 0;
		while(left < right) { //왼쪽 인덱스가 오른쪽을 넘어가지 않는 범위에서 탐색한다 
			int sum = arr[left] + arr[right];
			if(sum <= target) //합이 원하는 값보다 작다면 왼쪽 인덱스를 증가시킨다
            	left ++;
			else if(sum > target) //합이 원하는 값보다 크다면 오른쪽 인덱스를 감소시킨다
            	right --;
			if(sum == target) answer ++;
		}
		
		System.out.print(answer);
	}

}

이전 예시와 달라진 점만 주석으로 작성하였다. 왼쪽 인덱스를 증가시키거나, 오른쪽 인덱스를 감소시키므로 왼쪽 인덱스 < 오른쪽 인덱스일 때만 탐색을 진행한다.

 

참고

https://bbangson.tistory.com/72