[백준] 2003. 수들의 합2

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

2003번: 수들의 합 2

투 포인터로 풀면 된다. 주요 로직은 다음과 같다.

• 예를 들어 start가 2, end가 4이면 arr[2] + arr[3]의 합이 sum이 된다.
• 따라서 초기 값으로 start는 0, end는 1, sum은 arr[start]를 주었다.
• sum == m인 경우 카운트한다.
• sum <= m인 경우 end++를, sum < m인 경우 start++를 해준다. 그런데 이때 arr[end] 값을 sum에 더해주거나, arr[start] 값을 sum에서 빼주어서 sum 값을 계속 변경해주어야 한다.

그런데 내가 계속 실수했던 부분은 다음과 같다.

• while 문의 조건을 while(start < end && end <= n)로 설정했는데 계속 틀렸다. 결론적으로는 start < end 조건이 잘못됐다.
• 예를 들어 배열 값이 {6, 1, 4}이고 m이 5인 경우, 
  • start = 0, end = 1일 때 sum은 6으로 m보다 크다. 
  • 따라서 sum에서 arr[0]인 6을 빼주어 sum은 0이 되고, start는 start++로 1이 된다.
  • 그러면 이때 start와 end가 둘 다 1이므로 반복문을 빠져나오게 된다. 따라서 start와 end가 같아도 된다는 점을 놓쳤었다.
  • 어차피 start와 end가 같으면 sum이 0이므로, sum <= m 조건에 걸려서 end값이 1 증가하게 된다. 따라서 start가 end보다 커질 걱정을 하지 않아도 된다.

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

// 시간 복잡도: O(N)
public class Main {

    static int n;
    static int m;
    static int[] arr;
    static long answer = 0;

    public static void main(String[] args) throws IOException {

        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());
        }

        int start = 0;
        int end = 1;
        long sum = arr[start];
        while (end <= n) {
            if (sum == m) {
                answer++;
            }

            if (sum <= m) {
                sum += arr[end++];
            } else {
                sum -= arr[start++];
            }
        }

        System.out.println(answer);
    }
}