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

문제

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

2003번: 수들의 합 2

 

설명

수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구해야 한다.

일일이 부분합을 구해서 문제를 풀기 보다 시간복잡도를 줄이기 위해 투 포인터를 사용해 구한다.

두 개의 포인터를 각각 start와 end로 두고 둘 다 배열의 앞에서 시작한다.

현재 sum이 M보다 크거나 같고 end가 배열 끝에 도달했을 경우 현재 start가 가리키는 값을 빼고 start를 하나 전진시킨다. 현재 sum이 M보다 작다면 현재 end가 가리키는 값을 더하고 end를 하나 전진시킨다. 마지막으로 sum이 M과 같다면 num을 증가시킨다. 해당 과정을 start가 배열 끝에 도달하기 전까지 반복한다.

void twoPointer() {
    int sum = 0;
    int start = 0;
    int end = 0;

    while (start < N) {
        // sum이 M보다 크거나 같고 end가 배열의 끝에 도달했을 경우
        if (sum >= M || end == N)
            sum -= inputs[start++];
        // sum이 M보다 작을 경우
        else
            sum += inputs[end++];

        // sum이 M과 같을 경우
        if (sum == M)
            num++;
    }

    System.out.println(num);
}

 

전체 코드

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

public class Main {

    static int N, M, num;
    static int[] inputs;

    static void twoPointer() {
        int sum = 0;
        int start = 0;
        int end = 0;

        while (start < N) {
            // sum이 M보다 크거나 같고 end가 배열의 끝에 도달했을 경우
            if (sum >= M || end == N)
                sum -= inputs[start++];
            // sum이 M보다 작을 경우
            else
                sum += inputs[end++];

            // sum이 M과 같을 경우
            if (sum == M)
                num++;
        }

        System.out.println(num);
    }

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

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

        num = 0;

        twoPointer();
    }
}