[정리] 투포인터

투포인터

• 리스트에 순차적으로 접근해야 할 때 두개의 점의 위치를 기록하며 처리하는 알고리즘이다.

문제와 코드를 통해서 알아보겠다

• 백준 (2003번) 수들의 합 2

문제

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

풀이

package TwoPointer;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class NumberSum2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
//        투포인터  -> head   tail -> 중견기업 단골 문제다
//        1초 -> 몇번 컴퓨터가 10억
//        int -> 21억

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] number = new int[n];
        int ans = 0;

        st = new StringTokenizer(br.readLine(), " ");

        for (int i = 0; i < n; i++) number[i] = Integer.parseInt(st.nextToken());

        int left = 0;
        int right = 0;
        int sum = 0;
//        투포인터인 이유 -> 슬라이딩 윈도우 ->
        while (left <= right) {
            if (sum >= m) {
                sum -= number[left];
                left++;
            } else if (right >= n) {
                break;
            } else {
                sum += number[right];
                right++;
            }
            if (sum == m)
                ans++;
        }

//        head : 4 tail :6 -> 6
        System.out.println(ans);

    }
}