백준 2003번: 수들의 합 2

문제 설명

• https://www.acmicpc.net/problem/2003
• 수열의 연속된 숫자의 합이 M이 되는 경우의 수가 몇개인지 구하는 문제입니다.

접근법

• 연속된 숫자의 합은 투 포인터를 활용해 구할 수 있습니다.
  • 값을 뺄 때는 현재 위치의 값을 빼고 포인터를 이동시킵니다. arr[leftIdx++]
  • 값을 더할 때는 포인터를 이동시킨 뒤 해당 위치의 값을 더합니다. arr[++rightIdx]

투 포인터 누적합 수도코드

왼쪽 포인터 = 0;
오른쪽 포인터 = 0;
배열의 길이 = N;
누적 합 = arr[0];

while(왼쪽 포인터 < 배열의 길이){
	if(누적 합 > 조건 || 오른쪽 포인터가 끝에 도달){
    	왼쪽 값을 누적 합에서 빼고,
        왼쪽 포인터를 한 칸 이동
    } else if( 누적 합 <= 조건){
    	오른쪽 포인터를 한 칸 이동시키고
        해당 값을 누적합에 더함
    }
}

정답

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = 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 leftIdx = 0;
		int rightIdx = 0;
		int sum = arr[0];
		int answer = 0;
		while(leftIdx<N) {
			if(sum == K) answer++;
//			System.out.println(leftIdx+"||"+rightIdx+"||"+sum);
			if (sum > K || rightIdx == N-1){
				sum-=arr[leftIdx++];			
			}else if(sum<=K) {
				sum+=arr[++rightIdx];
			}
			
		}
		System.out.println(answer);
	}
}