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

#2003 수들의 합2

난이도 : 실버 3

유형 : 투 포인터

2003번: 수들의 합 2

▸ 문제

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

▸ 입력

첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

▸ 출력

첫째 줄에 경우의 수를 출력한다.

 

문제 풀이  

해당 문제는 투 포인터 기법으로 풀이해주면 된다. 투 포인터는 주어진 배열을 두 개의 포인터를 조작하면서 원하는 것을 얻는 기법이다.

 

📚 조건

• 배열 크기 N (1 <= N <= 10,000)
• 구하는 값 M ( 1 <= M <= 300,000,000)

 

만약 이 문제를 이중포문을 모든 연속 구간을 구하려한다면 O(N^2)의 시간복잡도가 발생할 것이다. 투 포인터 알고리즘을 활용하면 두 포인터가 각 N개의 구간에서 움직이기 때문에 2N으로 O(N)의 시간복잡도로 풀이할 수 있다.

 

포인터의 위치는 무엇을 탐색하느냐에 따라 달라진다. 해당 문제는 구간 합을 구하는 문제이기 때문에 두 포인터는 시작점 0에서 같이 탐색을 시작할 것이다.

 

두 포인터가 같은 방향으로 진행

예제 2번을 통해 시뮬레이션을 돌려보자.

 

n = 10, m=5, 원소의 갯수가 10개인 배열에서 구간 합이 5인 구간을 찾으면 된다.  빨간색은 s이고, 파란색은 e인 두 포인터는 시작점 0에서 같이 탐색을 시작한다.

s:0, e:0

 

e를 한 칸씩 움직여 s~e사이에 있는 원소들의 구간합을 구한다. sum :1

 

s:0, e:1

s:0, e:2

 

sum의 값이 m보다 크게 될 경우 e의 값을 조정하면 값이 더욱 커지기 때문에 s의 값을 이동해서 앞에 있는 원소들을 하나씩 빼준다. sum = 6 - 1(arr[s])

 

s:0, e:3

 

그러면 sum==m이 되므로 해당 구간에서 카운트를 해주면 된다. 

s:1, e:3

 

이와 같은 방식으로 계속 탐색을 해나가면 된다. 

 

e의 포인터가 배열의 끝(n)에 도착했을 때 이제 여기서 두 가지의 경우로 나누어진다.

1. 만약 sum>= m이면 아직 탐색할 구간이 남았으므로 s의 값을 이동해주면서 구간 탐색을 더해준다.
2. 만약 sum<m이면 더 이상 탐색해봤자 sum보다 큰 값은 안나오므로 반복문을 종료해주면 된다.

s:7, e:10

 

풀이 코드 

import java.io.*;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = 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 s=0, e=0, sum=0, cnt=0;
		while(true) {
			if(sum>=m) {
				sum -= arr[s++];
			}else if(e==n) break;
			else {
				sum += arr[e++];
			}
			if(sum==m) {
				cnt++;
			}
			
		}
		System.out.println(cnt);
	}
}