[알고리즘] 투 포인터(Two-Pointer Algorithm) 알고리즘

 

참고

https://m.blog.naver.com/kks227/220795165570

투 포인터(Two Pointers Algorithm), 슬라이딩 윈도우(Sliding Window) (수정: 2019-09-09)

 

 

투 포인터 알고리즘에 대해 알아보겠습니다.

 

가끔 브루트 포스로 문제를 풀다보면 N이 큰 경우에는 시간초과가 발생하게 되는데, 그 때 완전 탐색이 아닌 다른 방법으로 어떻게 풀까하다가 알게 된 알고리즘입니다.

 

★ 완전 탐색 시 시간 초과가 나는 경우 ★

 

1. 투 포인터 알고리즘 시도해보기

2. 이분 탐색 시도해보기(binary search)

3. dp(Dynamic programming) 시도해보기

4. 그리디(Greedy) 시도해보기

 

 

 

투 포인터 알고리즘이란?

 

말 그대로 배열을 가리키는 2개의 포인터를 이용해 원하는 값을 얻는 방식입니다.

 

1) 두 개의 배열에 두 개의 포인터

 

백준 1208번 부분수열의 합 2

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

1208번: 부분수열의 합 2

N/2 배열에 대해 각각 부분합을 구한 후 2개의 배열을 하나는 오름차순 정렬, 하나는 내림차순 정렬을 하여 각각의 배열의 포인터를 두어 계산하는 알고리즘입니다.

두 포인터가 가리키는 합의 크기가 원하는 값보다 작으면 오름차순 배열의 포인터를 +1, 원하는 값보다 크면 내림차순 배열의 포인터를 +1 하는 방식입니다.

 

2) 한 개의 배열에 두 개의 포인터

 

백준 2003번 수들의 합 2

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

2003번: 수들의 합 2

해당 문제를 브루트 포스 방식으로 풀면 시간 복잡도는 O(N^2)이 됩니다. 근데 N의 최대값이 10000이므로 100000000은 1억이 되어 0.5초만에 해결이 불가능해 시간 초과가 나게 됩니다.

 

그러므로 해당 문제는 투 포인터 알고리즘으로 해결해야 합니다!

배열을 가리키는 start와 end 포인터를 설정한 후, 

 

1) start ~ end까지의 합이 M보다 크거나 같으면 || end가 N의 끝에 도달했을 때, start ++;

2) start ~ end까지의 합이 M보다 작으면, end ++;

3) start ~ end까지의 합이 M과 같으면, 결과값 ++;

 

코드

 

//투 포인터 알고리즘 문제 풀이

import java.util.*;

public class N_2003 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner s = new Scanner(System.in);
		int N = s.nextInt();
		long M = s.nextLong();

		int[] A = new int[N];
		for (int i = 0; i < N; i++)
			A[i] = s.nextInt();

		long sum = 0;
		int start = 0;
		int end = 0;
		int result = 0;

		while (start < N) {
			if (sum == M) {
				result++;
				start++;
				sum -= A[start - 1];
			} else if (sum > M || end >= N) {
				start++;
				sum -= A[start - 1];
			} else if (sum < M) {
				end++;
				sum += A[end - 1];
			}
		}
		System.out.println(result);
	}

}

 

백준 1644번 소수의 연속합

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

1644번: 소수의 연속합

N이하의 소수를 에라토스테네스의 체를 이용하여 구하고, 해당 소수들을 배열에 넣어 배열을 대상으로 투 포인터 알고리즘으로 연속합을 구한다!

 

코드

 

//백준 1644번
//투 포인터 알고리즘 문제 풀이
//주어진 수 N이하의 소수를 모두 구한 후, 투 포인터 알고리즘 이용

package 백준;

import java.util.*;

public class N_1644 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner s = new Scanner(System.in);
		int N = s.nextInt();

		// 에라토스테네스의 체 이용해서 N 이하의 소수 찾기
		boolean[] A = new boolean[N + 1]; // false면 소수, true면 합성수
		ArrayList<Integer> prime = new ArrayList<Integer>();

		for (int i = 2; i <= N; i++) {
			if (A[i] == false) {
				for (int j = i + i; j <= N; j += i) {
					A[j] = true;
				}
			}
		}

		for (int i = 2; i <= N; i++) {
			if (A[i] == false)
				prime.add(i);
		}

		int start = 0;
		int end = 0;
		int result = 0;
		int sum = 0;

		while (start < prime.size()) {
			if (sum == N) {
				result++;
				start++;
				sum -= prime.get(start - 1);
			} else if (sum > N || end >= prime.size()) {
				start++;
				sum -= prime.get(start - 1);
			} else if (sum < N) {
				end++;
				sum += prime.get(end - 1);
			}
		}
		System.out.println(result);
	}

}

 

백준 1806번 부분합

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

1806번: 부분합

역시 연속된 부분합을 구하는 문제이고, 투 포인터를 두어 부분합이 S 이하이면 end++, S 이상이면 start++, end가 max일 때는 start++ 식으로 구현해주면 된다.

 

코드

//백준 1806번
//투 포인터 알고리즘 문제 풀이


import java.io.*;

public class N_1806 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			String[] input = br.readLine().split(" ");
			int N = Integer.parseInt(input[0]);
			long S = Long.parseLong(input[1]);

			int[] A = new int[N];
			String[] arr = br.readLine().split(" ");

			for (int i = 0; i < N; i++)
				A[i] = Integer.parseInt(arr[i]);

			long sum = 0;
			int start = 0;
			int end = 0;
			int result = 0;
			int min_length = Integer.MAX_VALUE;

			while (start < N) {
				if (sum >= S || end >= N) {
					if (sum >= S) {
						result++;
						if (min_length > end - start)
							min_length = end - start;
					}

					start++;
					sum -= A[start - 1];

				} else if (sum < S) {
					end++;
					sum += A[end - 1];
				}
			}

			if (result == 0)
				System.out.println(0);
			else
				System.out.println(min_length);
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

}

 

 

백준 2230번 수 고르기

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

2230번: 수 고르기

해당 문제는 앞의 문제들과는 조금 다르다. 부분합을 구하는 것이 아닌 차이가 M 이상인 두 개의 수를 구하는 것이다. (같은 수도 가능!) 하지만 투 포인터를 써서 같은 방식으로 구현해주면 된다.

 

먼저, 배열을 오름차순으로 정렬한 뒤,

 

두 수의 차이가 M 미만이면 end++, M 이상이면 start++, end가 max이면 start++ 식으로 구현해주면된다.

(오름차순 정렬이 key point!)

 

코드

//백준 2230번
//투 포인터 알고리즘 문제 풀이


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

public class N_2230 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			String[] input = br.readLine().split(" ");
			int N = Integer.parseInt(input[0]);
			int M = Integer.parseInt(input[1]);

			int[] A = new int[N];
			for (int i = 0; i < N; i++)
				A[i] = Integer.parseInt(br.readLine());
			
			Arrays.sort(A);

			int start = 0;
			int end = 0;
			int min = Integer.MAX_VALUE;

			while (start < N) {
				if (end >= N || Math.abs(A[start] - A[end]) >= M) {
					if (end < N) {
						if (min > Math.abs(A[start] - A[end]))
							min = Math.abs(A[start] - A[end]);
					}

					start++;
				} else if (Math.abs(A[start] - A[end]) < M) {
					end++;
				}
			}
			System.out.println(min);
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

}

 

 

백준 1484번 다이어트

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

1484번: 다이어트

현재몸무게^2 - 과거몸무게^2 = G를 만족하는 현재몸무게를 모두 구하면 된다. 현재몸무게와 과거몸무게 모두 모르는 변수이기 때문에 완전탐색해야 하는데 범위가 너무 크기 때문에 브루트 포스는 불가하다. 투 포인터를 활용하면 해결할 수 있다. 현재몸무게(기존의 end), 과거몸무게(기존의 start) 변수를 1로 초기화한 후, 현재몸무게^2 - 과거몸무게^2가 G 미만이면 end++, G 이상이면 start++, G이면 결과 출력하는 방식으로 구현!

 

코드

 

//백준 1484번
//투 포인터 알고리즘 문제 풀이

import java.util.*;

public class N_1484 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner s = new Scanner(System.in);
		int G = s.nextInt();

		int current = 1;
		int old = 1;
		int flag = 0;

		while (old < G) {
			if (current * current - old * old == G) {
				System.out.println(current);
				flag = 1;
				old++;
			} else if (current * current - old * old < G) {
				current++;
			} else if (current * current - old * old > G) {
				old++;
			}
		}
		if (flag == 0)
			System.out.println(-1);

	}

}