투 포인터. 수들의 합2

문제

A[i] + A[i + 1] + ... + A[j - 1] + A[j] = M이 되는 경우의 수를 구하는 문제. (구간 합)

해결방향성

투 포인터를 사용한다.
처음에 인덱스 0부터 양 포인터를 두고, end에 도달할때 까지 포인터를 증가시키며 구간합을 구한다.

코드

package twoPointer;

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

public class Main {
    static int N;
    static int M;
    static int[] array;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        array = new int[N];
        for (int i = 0; i < N; i++) {
            array[i] = Integer.parseInt(st.nextToken());
        }

        int sum = 0;

        int start = 0;
        int end = 0;
        int count = 0;

        while (true) {
            if (sum >= M){ // sum > M
                sum -= array[start++];
            } else if (end == N) {
                break;
            }
            else if (sum < M) { // sum < M
                sum += array[end++];
            }
            if (sum == M) {
                count++;
            }
        }

        bw.write(String.valueOf(count));

        bw.flush();
        br.close();
        bw.close();
    }
}

결론

사실 아직도 이 문제를 이해 못하겠다...

• while문의 분기문처리가 힘든 문제인데, sum > M 인 경우가 먼저 위치해야한다. 그 이유는 if - else if 문에서 end가 먼저 위치해버리면, end == N 일때 루프 탈출을 못하게 되어버려, 한번 더 돌게되어서 ArraysIndexOutOfBoundsException 에러가 발생할수있다. 그래서 sum > M을 먼저 위치시키고 다음으로 else if 문을 통해서 탈출문을 작성해준다. sum > M 이라는 뜻은 오른쪽에 많이 취우친 상태라는 것인데, 이때 end에 도달했다면 이미 더이상 볼필요가 없다는 소리이므로, 바로 else if (end == N)으로 리턴해준다. 반면에, sum < M이라는 소리는 아직 더할 수가 많이 필요하다는 소리이므로 계속 end인덱스가 증가할것이다. 하지만 그래도 end에 도달 할때 까지 sum < M인 경우, 더 이상 찾을 필요가 없으므로 역시 리턴해준다.
• 아직은 부족한거같다. 더 이해해서 작성해보도록 하겠다.