[BOJ] 2003번 수들의 합 2 Java 풀이

 

BOJ 2003 수들의 합 2

전형적인 투 포인터 문제다. 수열 하나에 포인터 두 개를 두고 탐색해주면 된다.  수열의 길이인 N의 최댓값이 10,000인데, 각 원소가 30,000을 넘지 않으므로 수열의 모든 원소를 합쳤을 경우에도 int의 범위에 해당해 처리하는데 문제가 없다. 마침 합으로 만들어야 하는 M의 경우에도 최댓값이 3억으로 알맞게 주어졌다. 시간 제한은 0.5초로 다른 문제와 비교해 길지 않은 편인데, 투 포인터로 배열 하나를 모두 돌아다녀야 2N으로 O(N)이고 최악의 경우 길이 10,000이라고 해도 20,000 번 안에 탐색이 끝나니까 0.5초면 충분하겠다.

주 풀이는 합에 포함할 범위의 처음과 끝을 나타내는 포인터 2개(start, end), 합을 저장할 변수 1개(sum), 합이 M과 같을 경우의 수를 세는 변수 1개(cnt)로 진행했다.

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

public class Main {
	static int N, M;
	static int arr[];
	static int start, end, sum, cnt;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		arr = new int[N+1];
		
		st= new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		start = 0; end = 0; sum = arr[0]; cnt = 0;
		
		while(true) {
			if(sum == M) {
				sum -= arr[start++];
				sum += arr[++end];
				cnt++;
			}else if(sum < M) {
				sum += arr[++end];
			}else {
				sum -= arr[start++];
			}
			
			if(end == N) {
				break;
			}
		}
		
		System.out.println(cnt);
	}

}

 

모든 수가 자연수이기 때문에 원소 하나를 넣으면 합이 반드시 커지고, 원소 하나를 빼면 반드시 작아진다. 그래서 수열의 맨 앞에서부터 시작하면서 합이 M보다 작으면 범위를 뒤로 하나 확장시키고, 합이 M보다 크면 앞 범위를 하나 당기면서 M값과 sum값의 비교를 진행한다. 만약 sum == M인 상황의 경우 범위를 뒤로 하나 확장시키면 반드시 M보다 큰 값이 나오고, 앞 범위를 하나 당기면 반드시 M보다 작아지므로 불필요한 과정을 없애기 위해 두 포인터를 모두 +1 이동시켰다. 

모든 수가 자연수이므로 투포인터를 사용할 수 있었다. 만약 음수가 포함된 수열이었다면 백트래킹 dfs를 사용해 풀었어야 했을 것이다.