투 포인터 알고리즘

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

2003번: 수들의 합 2

 

백준에 예제에서 한번 배워보자

 

투포인터 알고리즘이란 두개의 포인터지점을두어 특정 조건일때 rear값을 상승시키면서 중첩해가면서 계산하다가 답이아닌경우 front 증가시키면서 정답을 찾아가는 방법이다. 수들의합 2의 예제 2번으로 예시를 들겠다.

 

 

현재 구하는 M = 5라고 한다면 front =0 , rear = 0 을 가리키는 상태이다.

 

이때 sum = 1 이된다. 

 

구할려는 M =5 이므로 sum < M 이므로 rear 값을 증가시킨다.

 

rear =1 이되고 sum 3 이된다. 마찬가지로 sum < M 이므로 rear 값을 증가시킨다.

sum = 6이된다.  이제 sum > M 보다 크다 이때는 front의 값을 sum에서 제거해주고 front를 1증가시켜준다.

이제 sum =5다. 따라서 카운터를 1증가시킨다. 그리고 sum = 5이기때문에 rear를 1증가시키거나 front을 1증가시키면된다. 나는 rear를 증가시키겟다.

 

sum = 9가된다. 앞선 반복을 하면서 카운트를 증가시키면 되는데 주의할점은 sum > M 보다 커서  front를 증가시킬때

 

front > rear 보다크다면 rear = front 로 맞추어주면된다.

 

또한 rear = N 일때에는 sum < M 보다 작은상태니 front를 증가시켜도 의미가없으니 종료시킨다.

 

package day0405;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class B2003 {
    static int N, M;
    static int A[];
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        A = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
 
        int front = 0;
        int rear = 0;
        int sum = 0;
        int cnt = 0;
        while (true) {
            if(sum>= M) sum-=A[front++];
            else if(rear == N)break;
            else sum +=A[rear++];
            
            if(sum == M )cnt++;
        }
 
        System.out.println(cnt);
    }
}