투 포인터(Two Pointer)

투 포인터 알고리즘

• 1차원 배열에서 두 개의 포인터를 조작해가면서 원하는 결과를 얻는 알고리즘이다.
• 투 포인터 알고리즘을 이용해 O(N^2)에서 O(NlogN)으로 개선할 수 있다.

 

예시

• SUM =5 인 경우의 수 구하기

• 위의 과정을 배열의 인덱스가 N일때 즉 모두 확인했을 때 반복문 종료!

 

코드

package twoPointer;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_BJ_2003_수들의합2 {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        
        int [] arr = new int[N];
        
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        int start=0, end=0, sum=0, cnt=0;
        while(true) {
            if(sum>=M) sum -= arr[start++];
            else if(end==N) break;
            else sum += arr[end++];
            
            if(sum==M) cnt++;
        }
        System.out.println(cnt);
    }
 
}