[알고리즘/Java] 투 포인터(Two Pointers)

[ 1 ] 기본내용

"투 포인터"는 1차원 배열에서 각기 다른 원소를 가리키는 2개의 포인터를 활용하여 원하는 값을 얻는 알고리즘이다. 이때, 포인터는 C/C++에서의 포인터가 아닌 배열에서의 "인덱스"를 의미한다.

 

2개의 포인터를 적절히 이동시키며 시간 복잡도를 최적화할 수 있는 것이 투 포인터 알고리즘의 핵심이다.

 

투 포인터가 자주 활용되는 문제로는

(1) target 값을 미리 설정하고, 특정 배열 내에 target 값과 같은 - 유사한 부분 합이 몇 개 존재하는지 계산하는 문제

(2) 배열 내 target = arr[i] + arr[j] 를 만족하는 (i, j) 쌍이 몇 개 존재하는지 계산하는 문제

등이 있다.

 

[ 2 ] 부분 합에서의 투 포인터

해당 내용은 대표 예제인 백준 2003번을 통해 살펴보도록 하자.

문제 출처: https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2

 

해당 문제는 구간 합(Prefix Sum)을 구하여 해결할 수도 있지만, 그럴 경우 이중 for문을 사용해야 하므로 시간 초과가 발생한다. 이때 투 포인터를 활용하면 시간복잡도를 최적화할 수 있다.

 

< 투 포인터의 기본 의미 >

- 두 개의 포인터 start와 end는 부분 배열의 시작과 끝을 의미한다.

- 두 개의 포인터 start와 end는 둘 다 0에서부터 시작하며, 항상 start <= end를 만족해야 한다.

 

S를 start와 end 사이의 부분 합, M을 target 값이라 가정하자.

 

< 알고리즘 실행 과정 >

- start와 end가 N(배열의 크기)에 도달할 때 알고리즘이 끝난다.

- S > M 인 경우 or end가 이미 N에 도달한 경우

  ▶ 범위를 좁히기 위해 start++ 를 한다. 

- 그렇지 않은 경우

  ▶ 범위를 넓히기 위해 end++를 한다.

- S == M 인 경우

  ▶ 우리가 찾는 값이므로 cnt++를 한다.

 

다음 그림을 통해 위 과정을 이해해보자.

 

파란 포인터가 start, 빨간 포인터가 end이다.

(1) start = end = 0. start = end일 경우 부분 배열의 합은 0이다. S < M 이므로 end++를 한다.

 

(2) 아직 S < M 이므로 end++

(3) 아직 S < M 이므로 end ++

(4) 이제 S > M 이므로 start++ 를 한다.

(5) S = M 이므로 cnt++를 한다.

(6) S > M 이므로 start++

(7) S > M 이므로 start++

(8) S < M 이므로 end++

(9) S > M 이므로 start++

(10) S < M 이므로 end++

(11) S > M 이므로 start++

(12) S = M 이므로 cnt++를 한다.

 

위와 같은 과정을 start와 end가 N(배열의 크기)에 다다를때까지 반복하면 cnt = 3이 나온다.

소스코드는 다음과 같다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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 start = 0;
		int end = 0;
		int cnt = 0;
		int sum = 0;
		
		while(!(start == N && end == N))
		{
			if(sum > M || end == N)
			{
				sum -= arr[start++];
			}
			else
			{
				sum += arr[end++];
			}
			
			if(sum == M)
			{
				cnt++;
			}
		}

		System.out.println(cnt);
		
	}

}

 

투 포인터 알고리즘은 start와 end가 0에서 N에 다다르면 끝이 난다는 점에서 시간복잡도가 O(N)이다. 

 

[ 3 ] 배열 내 target = arr[i] + arr[j] 찾기

위의 부분 합뿐만 아니라, 두 개의 원소를 활용하여 target을 찾을 때에도 투 포인터를 활용할 수 있다.

 

과정은 다음과 같다.

 

<기본 설정>

- 배열이 정렬되어 있어야 한다.

- start = 0, end = N-1에서 시작한다.

 

<알고리즘 실행 과정>

- arr[start] + arr[end] > target

  ▶ end-- 를 한다. 정렬되어 있으므로 큰 수를 줄여 target에 가까워지도록 하기 위함이다.

- arr[start] + arr[end] < target

  ▶ start++를 한다. 

- arr[start] + arr[end] = target

  ▶ cnt++를 한 후 start++, end--를 한다.

 

위 과정을 start < end 를 만족하는 동안 반복한다.

 

문제 출처: https://www.acmicpc.net/problem/1940

1940번: 주몽

이 문제를 통해 본 알고리즘을 연습할 수 있다.