[백준] 2003. 수들의 합2 (Java)

 

🔒 문제

2003번: 수들의 합 2

 

 

🔑 알고리즘

투 포인터

 

 

💡  풀이

투 포인터를 이용하여 O(N)의 시간 복잡도로 해결할 수 있다.

 

범위의 시작을 의미하는 포인터 S와 끝을 의미하는 포인터 E를 모두 배열의 맨 앞에 두고

두 포인터 사이의 배열 값의 합이

M보다 작다면 값을 늘려야하므로 E를 오른쪽으로 한 칸 움직이고,

M보다 크다면 값을 줄여야하므로 S를 오른쪽으로 한 칸 움직이고,

M과 같다면 count를 1 증가시키고 S를 오른쪽으로 한 칸 움직인다.(E도 무관)

 

M이 배열의 끝에 닿을 때까지 이 과정을 반복한다.

 

이때 두 포인터가 한 번에 한칸씩만 움직이면서

E가 움직이면 새로운 값을 더해주고 S가 움직이면 기존의 값을 빼주면 된다.

 

 

✏️ 코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int s = 0;
		int e = 0;

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int[] arr = new int[n + 1];

		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < n; i++)
			arr[i] = Integer.parseInt(st.nextToken());

		int sum = arr[0];
		int count = 0;
		if(sum == m) count++;
		
		while (true) {
			
			if (sum < m) sum += arr[++e];
			else if (sum >= m) sum -= arr[s++];

			if (e == n) break;
			if(sum == m) count++;
		}

		System.out.println(count);
	}
}