[Algorithm] Two Pointer 의미 및 활용

1. 의미

정렬된 리스트를 두 개의 포인터를 이용해 순차적으로 접근하면서 두 포인터 구간의 값이 타겟 값과 같을 때 까지 포인터를 조작하는 기법을 말한다.

 

2. 활용

- 배열의 특정 연속된 구간을 처리하는 경우

1) 문제에서 연속된 데이터 구간을 처리하기 원한다면?

2) 다양한 접근 방법을 떠올려 보는 것이 중요

3) 자주 사용되는 기법들로는 어떤 것이 있을까?

 

 

3. 예시

1) 부분 수열의 합

수열 : 1, 2, 3, 2, 5

합이 5인 부분 연속 수열의 개수는?

 

int[] arr = {1,2,3,2,5};
        int len = arr.length;
        int end = 0, sum=0,d_sum = 5;
        int cnt=0;
        
        for(int st = 0;st<len;st++) {
        	while(sum < d_sum && end<len) {
        		sum+=arr[end];
        		end++;
        	}
        	if(sum == d_sum)
        		cnt++;
        	sum-=arr[st];
        }
        System.out.println(cnt);

 

2) N개의 정수, M개의 쿼리 정보(L, R로 구성, 이 구간에 해당하는 데이터의 합 구하기)

* 백준 문제 예시

www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

 

- 풀이 코드

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

public class Main {
   
	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        //선언 및 입력
        int N,M, arr[];
        ArrayList<Integer> prefix = new ArrayList<Integer>();
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N];
        st = new StringTokenizer(br.readLine()," ");
        for(int i=0;i<N;i++)
        	arr[i] = Integer.parseInt(st.nextToken());
        	
        
        //prefix sum 구하기
        int sum=0;
        prefix.add(0);
        for(int i=0;i<N;i++) {
        	sum+=arr[i];
        	prefix.add(sum);
        }
        //부분 합 구하기
        for(int i=0;i<M;i++) {
        	int from, to;
        	st = new StringTokenizer(br.readLine()," ");
        	from = Integer.parseInt(st.nextToken());
        	to = Integer.parseInt(st.nextToken());
        	sb.append((prefix.get(to)-prefix.get(from-1))+"\n");
        }
        System.out.println(sb);
        
    }
}