(Java) 백준 2003 - 수들의 합 2

다른 문제를 풀면서 투 포인터 알고리즘에 대해 알게 되었고

대표적인 문제를 풀어 보았다. 실버 4 문제라 기본적인 투 포인터 개념만 이해한다면

바로 풀 수 있는 문제이다.

 

투 포인터 알고리즘은 연속되고 길이가 가변적인 부분 배열을 만들어 특정 조건을 만족시키는 알고리즘이다.

배열을 반복적으로 탐색할때 2중 for문을 이용한다면 시간 복잡도가 O(n^2) 나온다.

그러나 투포인터 알고리즘을 이용한다면 시간 복잡도를 O(n)까지 줄일 수 있다.

 

투 포인터 알고리즘의 방식은 두 가지가 있다.

1. 시작점과 끝점이 배열의 시작점에서 같이 시작하는 것

2. 정렬된 배열 안에서 시작점과 끝점이 각각 배열의 시작점과 끝점에서 시작하는 것

 

이 문제는 첫 번째 방식으로 접근하여 풀었다. 간단하면서도 강력한 알고리즘이라 조건만 맞는다면

자주 사용할 것 같다. 비슷한 개념인 슬라이딩 윈도우를 이용한 문제도 풀어볼 생각이다. 

 

최종 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] arr = new int[n];

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

        int start = 0;
        int end = 0;
        int sum = 0;
        int cnt = 0;

        while (start < n) {
            if (sum > m || end == n) {
                sum -= arr[start];
                start++;
            } else {
                sum += arr[end];
                end++;
            }
            if (sum == m) {
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}