투 포인터(Two Pointer)

  투 포인터는 1차원 배열에서 선형시간에 2개의 배열요소(인접 할 경우 2개 이상의 배열요소)를 이용하여 문제를 해결해야 하는 경우 사용한다. 

 

  2개의 배열요소를 이용한다는 것은 2개를 비교한다는 것을 의미한다. 보통의 방식으로는 배열에서 요소 2개를 배교하면 시간복잡도 O(N^2)로 풀게 되는데, 왜냐하면 모든 배열 요소들을 처음부터 끝까지 확인해야 하기 때문이다.

 

  하지만, 이전에 방문한 것을 다시 방문하지 않는 투 포인터 방식을 사용하면 O(N)만에 해결이 가능하다.

 

  투 포인터의 포인터는 당연하게도 C언어와 관련한 포인터가 아닌 배열의 특정 원소위치를 가리키는 것을 의미한다.

 

  기본적인 개념을 넘어가고 백준 알고리즘에서 풀었던 문제에 대한 팁을 몇가지 적는다.

 

 

2003번: 수들의 합 2

import java.util.*;

public class Main {
	public static int solution(int[] array, int value) {
		int S=0;
		int E=0;
		int num=0;
		while((S<array.length && E<array.length)) {
			int sum = sum(array, S, E);
			if(sum==value) {
				num++;
				E++;
			}
			else if(sum>value) {
				S++;
			} 
			
			else if(sum<value) {
				E++;
			}
		}
		return num;
	}
	
	public static int sum(int[] array, int start, int end) {
		int res=0;
		for(int i=start; i<=end; i++) {
			res += array[i];
		}
		return res;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		int value = sc.nextInt();
		int[] array = new int[num];
		for(int i=0;i<num;i++) {
			array[i] = sc.nextInt();
		}
		int res = solution(array, value);
		System.out.println(res);
	}
}

 배열의 맨 처음을 가리키는 S와 E를 설정했으며,

sum이 value보다 크면 S++, sum이 value보다 작으면 E++을 한다.

E++을 함으로, 배열의 요소가 하나 늘어나기 떄문에 sum이 증가한다.

S++을 함으로, 배열의 요소가 하나 줄어들기 때문에 sum이 감소한다.

S, E는 뒤로 다시 돌아가지 않고 앞으로만 계속 이동하여 문제를 해결하는 것이 핵심이다.

가장 기본적인 투포인터 문제이다.

 

 

1644번: 소수의 연속합

import java.util.*;

public class Main {

	public static int solution(int num) {

		int cnt = 0;

		int S = 0;
		int E = 0;
		int[] array = makePrime(num);
		while (S < array.length && E < array.length) {
			int res = sum(array, S, E);
			if (res == num) {
				cnt++;
				E++;
				continue;
			}

			if (res < num) {
				E++;
				continue;
			}

			if (res > num) {
				S++;
				continue;
			}
		}
		return cnt;
	}

	public static int sum(int[] array, int S, int E) {
		int res = 0;
		for (int i = S; i <= E; i++) {
			res += array[i];
		}
		return res;
	}

	public static int[] makePrime(int num) {
		int[] arr = new int[4000000];
		int k = 0;
		for (int i = 2; i <= num; i++) {
			if (checkPrime(i)) {
				arr[k++] = i;
			}
		}

		int[] array = new int[k];
		for (int i = 0; i < k; i++) {
			array[i] = arr[i];
		}

		return array;
	}

	public static boolean checkPrime(int num) {
		for (int i = 2; i <= Math.sqrt(num); i++) {
			if (num % i == 0) {
				return false;
			}
		}
		return true;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		int ans = solution(num);
		System.out.println(ans);
	}

}

  2003번 문제와 비슷한대 소수를 배열로 만드는 과정이 가장 핵심이다.

에라토스테네스의 체의 방식으로 소수를 빠르게 구할 수 있다.

어떤 자연수 N이 소수라면, 1과 자신을 제외하고는 어떠한 자연수의 배수가 되어서는 안된다.

 

예를 들어, 16이 소수인지 판별한다면 어떠한 자연수의 배수도 될 수 없으므로 9~15로 나눌 필요가 없다.

16을 2,3,4로 나누어서 나머지가 0인지 확인하면 된다.

즉, 2부터 자신의 제곱근값까지만 나누어서 나머지가 있는지 없는지 확인하면 된다.

41도 마찬가지로, 6~39을 나눠서 나머지를 확인하지 않아도, 2부터 자신의 제곱근인 6까지만 검사하면 된다. 

 

또한 배열의 크기는 입력된 숫자에 따라 유동적으로 만들어야 메모리, 시간을 효율적으로 사용할 수 있다.

 

 

2230번: 수 고르기 

import java.util.*;

public class Main {
	public static int solution(int[] array, int value) {
		int S=0;
		int E=0;
		int num=2000000000;
		Arrays.sort(array);
		while((S<array.length && E<array.length)) {
			int res = diff(array,S,E);
			if(res>=value && res<=num)
				num=res;
						
			if(res>=value) {
				S++;
			} else {
				E++;
			}
		}
		return num;
	}
	
	public static int diff(int[] array, int start, int end) {	
		return Math.abs(array[start]-array[end]);
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		int value = sc.nextInt();
		int[] array = new int[num];
		for(int i=0;i<num;i++) {
			array[i] = sc.nextInt();
		}
		int res = solution(array, value);
		System.out.println(res);
	}
}

이 문제는 합이 아닌 차에 대한 문제이다. 연속된 수들이 아닌 2개의 숫자만 고르기 때문에 S,E는 배열의 마지막 위치까지 자동적으로 이동하지 않는다. 따라서 Arrays.sort(array)를 통해 강제적으로 오름차순을 해주어야 비교에 따라 S, E가 배열의 마지막 위치까지 이동한다. 

 

1484번: 다이어트

import java.util.*;

public class Main {

	public static int[] solution(int num) {
		int value = (int) Math.sqrt(num);

		int S = 1;

		int E = value+1;
		int cnt = 0;

		int[] tmp = new int[100];
		while (E-S>=1) {
			int val = cal(S, E);
			if (val == num) {
				tmp[cnt++] = E;
				E++;
			}

			else if (val > num)
				S++;

			else if (val < num) {
				E++;
			}
		}
		if (cnt == 0) {
			int[] ans = { -1 };
			return ans;
		}

		int[] ans = new int[cnt];
		for (int i = 0; i < cnt; i++) {
			ans[i] = tmp[i];
		}
		return ans;
	}

	public static int cal(int S, int E) {
		return (E*E - S*S);
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		int[] res = solution(num);
		for (int i = 0; i < res.length; i++) {
			System.out.println(res[i]);
		}
	}

}

 이 문제도 연속된 배열을 다루지 않고 2개의 값을 선택하여 해결해야 한다.

정해진 1차원 배열이 있지 않기 때문에 오름차순으로 숫자를 증가시켜서 값을 비교해야 한다.

배열에 대한 조건은 E-S>=1로 몸무게는 1이상이기 때문에 E가 계속 큰 값을 가지게 한다.

몸무게보다 결과값이 크면, S를 증가시켜서 결과값을 줄이고

몸무게보다 결과값이 작으면, E를 증가시켜서 결과값을 늘린다