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

 

◇  설명

   □  정의, 특징

      -  말 그대로 두 개의 포인터를 이용하는 것
      -  1차원 배열 안에서 각자 다른 원소를 가리키는 두 포인터를 조작해가며 결과 값을 얻음
      -  보통 left 포인터와 right 포인터가 양 끝단에서 시작하여 한 칸씩 이동하며
         중간에서 만날 때까지 탐색하는 방식 ( 아닌 경우도 있음 )
      -  필요에 따라 배열을 정렬한 뒤에 탐색하기도 한다
       ( 이진 탐색은 반드시 배열이 정렬된 상태에서 해야 함 ) 
      -  최악의 경우 O(n) 시간 소요  ( 이진 탐색은 O(log n) 시간을 보장 )

 

◇  코드

  Q.  n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

( https://www.acmicpc.net/problem/3273 )

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

public class Main_3273 {

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int a[] = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++)
			a[i] = Integer.parseInt(st.nextToken());
		int x = Integer.parseInt(br.readLine());
		br.close();

		Arrays.sort(a);

		int left = 0, right = n - 1, cnt = 0;
		while (left < right) {
			int sum = a[left] + a[right];
			if (sum <= x) {
				if (sum == x) cnt++;
				left++;
			} else
				right--;
		}

		System.out.println(cnt);
	}

}

  Q.  N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

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

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

public class Main_2003 {

	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()), m = Integer.parseInt(st.nextToken());
		int a[] = new int[n];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++)
			a[i] = Integer.parseInt(st.nextToken());
		br.close();

		int left = 0, right = 0, sum = 0, cnt = 0;
		while (true) {
			if (sum >= m) {
				if (sum == m) 	cnt++;
				sum -= a[left++];
			} else {
				if (right == n) break;
				sum += a[right++];
			}
		}

		System.out.println(cnt);
	}

}