BOJ 2003 수들의 합 2 [Java]

BOJ 2003 수들의 합2

- 문제 링크

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

- 문제 해설

전형적인 투포인터 알고리즘을 이용할 수 있는 문제이다.
2중 for문을 이용하면 시간 복잡도가 O(N^2)으로 제한 시간을 맞출 수 없지만, 투 포인터를 이용하면 O(N)으로 시간이 충분하다.
시작점을 가리키는 포인터를 start, 끝 점을 가리키는 포인터를 end, 포인터가 가리키는 두 원소의 합을 sum, 찾고자 하는 경우의 갯수를 cnt라고 하자.

1) 두 원소의 합이 M이면 구하고자 하는 경우를 찾았으니 cnt를 1 더해준다. start가 가리키는 원소의 값을 sum에서 빼주고 start를 1 더해준다. end를 1 더해주고 더해진 end가 가리키는 원소의 값을 sum에 더해준다.
2) 두 원소의 합이 M보다 작으면 end를 1 더해주고 더해진 end가 가리키는 원소의 값을 sum에 더해준다.
3) 두 원소의 합이 M보다 크면 start가 가리키는 원소의 값을 sum에서 빼주고 start를 1 더해준다.
4) end가 N이 될 때까지 위 과정을 반복한다.

- 코드 보기

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

public class Main
{
    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());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] arr = new int[n+1];

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

        int cnt = 0, start = 0, end = 0, sum = arr[0];

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

            if (end == n)
                break;
        }

        bw.write(Integer.toString(cnt));
        br.close();
        bw.flush();
        bw.close();
    }
}