[Algorithm/Java][백준] 1806번 부분합

[BOJ] 1806번 부분합

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

문제 접근

투 포인터를 이용해서 문제를 풀었다.
deque와 이분 탐색을 이용해서도 풀 수 있다고 하는데 분류가 투 포인터라서 투 포인터를 사용해서 풀었다.
start와 end인 두 개의 인덱스를 사용하고 sum이 t(목표 값)보다 작거나 같으면 end를 +1해서 한개를 더 더하도록 하고, sum이 t(목표 값)보다 크면 start를 +1 해서 합에서 한개를 빼서 목표 값에 접근하도록 한다.
투 포인터를 사용하게 되면 O(N)으로 문제를 해결할 수 있게 되는 장점이 있다.

Code

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

public class BOJ1806 {
    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 t = 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 = arr[0];
        int answer = Integer.MAX_VALUE;
        while(start<=end){
            if(sum >= t){
                answer = Math.min(answer, end - start + 1);
            }
            if(sum <= t){
                end++;
                if(end == n) break;
                sum += arr[end];
            } else {
                sum -= arr[start];
                start++;
                if(start == n) break;
            }
        }
        if(answer == Integer.MAX_VALUE) System.out.println(0);
        else System.out.println(answer);
    }
}