[코딩테스트][알고리즘] 7. 투 포인터(Two Pointers)

 

 

 이 알고리즘은 소프트웨어 마에스트로 11기 온라인 코딩 테스트에서 출제되었다.

 

투 포인터는 1차원배열에서 서로 원소를 가르키는 2개의 포인터를 이용하는 알고리즘이다.

 

아래 문제는 투포인터의 대표적인 유형이다.

https://www.acmicpc.net/problem/2003

 

1차원 배열의 구간합(M)을 구하는 문제인데 푸는 방식은 이러하다.

 

1차원 배열 arr과 구간합의 시작과 끝을 가르키는 포인터 (s,e)를 준비한다.

arr = { 1 , 3 , 5 , 2 , 1 , 2 , 3 , 4 }

 

1. 초기값은 s=e=0 이다.

2. 항상 s<=e 이다.

3. s=e=0 일때의 구간합은 0이다.

 

1. 현재 구간합이 M 이상 or e=N 일때 ++s 

2. 1번이 아닌 경우 ++e

3. 현재 구간합이 M일때 ++result

 

이를 코드로 구현하면 다음과 같다.

 

import java.io.*;
import java.util.*;

public class Main {

	static int N, M, result;
	static int[] arr;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		arr = new int[N+1];

		st = new StringTokenizer(br.readLine());

		for (int i = 0; N > i; ++i) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		int s = 0;
		int e = 0;
		int temp = 0;
		
		while (true) {
			if (temp >= M)
				temp -= arr[s++];	// s를 오른쪽으로 옮긴 후 구간합에서 빼준다.
			else if (e == N)
				break;
			else
				temp += arr[e++];   // e를 오른쪽으로 옮긴 후 구간합에서 더해준다.
			if (temp == M)
				++result;
		}

		System.out.print(result);

	}

}