[알고리즘/JAVA] 투포인터 알고리즘

투포인터 알고리즘을 소개하고자 한다.

코딩 테스트에 많이 나오는 유형이라서 알면 매우 좋을 것 같다.

그럼 고고~

---

투포인터 알고리즘

투포인터는 선형 시간으로 알고리즘을 풀 수 있게 만들어주는 마법의 알고리즘이다. 하지만 매우 간단해서 구현도 할 만하다. 알기만 하면 그냥 써먹으면 된다!

투포인터는 연속적인 값들을 이용해 푸는 문제에 적합하다. 

2003번: 수들의 합 2

일단 백준 2003 문제를 읽고 오자. 간단하니까 금방 읽을 수 있다.

이 문제는 정수로 된 배열이 주어지고, 연속된 구간에서 합이 일정 값과 같다면 카운트를 올려서 정답을 출력해야 한다. 이 문제에서 선형 시간인 O(n)으로 풀 수 있는 투포인터 알고리즘을 적용해보자.

 

풀이 방법

1. 배열의 하나의 인덱스를 가리키는 Start 점과 End 점 두 개를 만들자.(start는 시작 지점, End는 끝점을 가리킨다.)
2. 처음 start와 end는 0으로 초기화해준다.
3. start 점부터 end점까지의 합을 구해서 sum에 저장해준다. (처음 sum은 0에서 0까지니까 배열의 0번째 인덱스 값이 저장된다.)
4. 배열을 도는데 세 가지 조건으로 돈다.
   1. sum == 찾고자 하는 값 --> 값을 만족하는 구간을 찾았으니 cnt(카운트 개수)를 하나 늘려주고, sum의 값에서 start인덱스의 값을 빼주고 1을 늘려준다. 그리고 end값을 1을 더한 후 그 인덱스의 값을 sum에 더해준다. (말이 좀 복잡한데 직접 문제를 생각해보면 뭔 말인지 이해할 것이다.)
   2. sum < 찾고자 하는 값 --> sum이 더 작으니까 값을 늘려주어야 한다. start 값은 그대로 두고, end 값을 1 늘려주고 그 end 인덱스의 값을 sum에 더해준다.
   3. sum > 찾고자 하는 값 --> sum이 더 크니까 값을 줄여주어야 한다. end 값은 그대로 두고, start 인덱스 값을 sum에서 빼주고 start값을 1 늘려서 갱신해준다.
5. 루프를 탈출하는 경우는 start 값이나 end 값이 배열의 인덱스를 초과하면 예외처리를 통해 탈출한다.(이 방법은 권장하지 않으니 다른 방법을 생각해보기 바란다.)

풀이 코드

package Baekjoon2;

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

public class Baekjoon_2003_수들의합2 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer token = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(token.nextToken());
		int M = Integer.parseInt(token.nextToken());
		token = new StringTokenizer(br.readLine());

		int[] arr = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(token.nextToken());
		}
		int cnt = 0;
		// 1.배열의 하나의 인덱스를 가리키는 Start 점과 End 점 두개를 만들자.(start는 시작지점, End는 끝점을 가리킨다.)
		// 2.처음 start와 end는 0으로 초기화해준다.
		int start = 0;
		int end = 0;

		int sum = 0;
		// 3. start 점부터 end점까지의 합을 구해서 sum 에 저장해준다.
		for (int i = start; i <= end; i++) {
			sum += arr[i];
		}
		for (int i = 0;; i++)
			try {
				if (sum == M) {
					cnt++;
					sum = sum + arr[++end] - arr[start++];
				} else if (sum < M) {
					sum += arr[++end];
				} else {
					sum -= arr[start];
					start++;
				}

			} catch (Exception e) {
				break;
			}
		System.out.println(cnt);
	}

}

투포인터 그림 설명

배열 {1,2,3,2,5}에서 합이 5인 부분 연속 수열을 찾는 문제를 그림으로 설명하겠다.

 

sum의 값이 5보다 작다. end를 1 늘려준다.

sum의 값이 여전히 5보다 작다. end를 1 늘려준다.

 

sum의 값이 5보다 크다. start의 값을 1 늘려준다.

 

드디어 sum의 값이 5와 같다. cnt에 1을 더해주고 start,end 둘 다 1 늘려준다.

sum의 값이 또 5와 같다. cnt에 1을 더해주고 start,end 둘 다 1 늘려준다.

sum의 값이 5보다 크다. start의 값을 1 늘려준다.

sum의 값이 5와 같다. cnt에 1을 더해주고 start,end 둘 다 1 늘려준다.

범위를 벗어나게 되면 탈출한다. 끝!

---

결론

투포인터는 코딩 테스트에 정말 자주 등장하는 알고리즘이다. 개념도 그렇게 어렵지 않으니 한번 익혀놓으면 좋을 것 같다!!

다들 열심히 해서 높은 곳에서 만났으면 좋겠다. 그럼 안녕...