[백준] 2003 수들의 합2 java

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

2003번: 수들의 합 2

 

투 포인터 알고리즘

리스트에서 두 개의 포인터를 이용해 순차적으로 접근합니다.

1. 첫 번째 원소와 마지막 원소에서 시작하는 경우

2. 둘 다 첫 번째 원소에서 시작하는 경우

 

문제 풀이 :

투 포인터에서, 2. 둘 다 첫 번째 원소에서 시작하는 경우를 사용하였습니다.

start = 0, end = 0 으로 시작합니다. 투 포인터는 start <= end 여야 합니다.

 

start < n까지 반복합니다.

1. 구간 합(sum)이 M을 초과하거나, end가 배열의 범위를 넘으면

   sum-arr[start] , start 오른쪽 한칸 이동을 해줍니다.

2. 구간 합(sum)이 M과 같거나 이하일때, end가 배열의 범위를 넘지 않을 때

   sum+arr[end] , end 오른쪽 한칸 이동 해줍니다.

만약 구간합(sum)이 M과 같다면 결과(count)를 증가시켜줍니다.

import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[] arr = new int[N];
		
		for(int i = 0; i<N; i++) {
			arr[i] = sc.nextInt();
		}
		int start = 0, end = 0, count = 0, sum = 0;
		
		while(start < N) {
			if(sum > M || end == N) sum-=arr[start++];
			else sum+=arr[end++];
                
			if(sum==M) count++;
		}
		
		System.out.println(count);
	
	
	}
}