[백준/BOJ] 1806 부분합 - JAVA

[백준/BOJ] 1806 부분합 - JAVA

문제

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

 

문제 분석

조건

10,000개 이상의 자연수로 이루어진 수열에서, 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 문제

풀이방법

투 포인터(슬라이딩 윈도우)를 활용하여 문제를 풀었다. `end`포인터를 한칸씩 옮기며 구간 합을 계산하였고, 조건이 만족했을 때 start를 옮기며 최소 길이를 비교하였다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int S = 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 sum = 0;
        int answer = N + 1;

        // end 포인터가 배열의 끝까지 이동
        for (int end = 0; end < N; end++) {
            sum += arr[end];
            while (sum >= S) {
                answer = Math.min(answer, end - start + 1);
                sum -= arr[start];
                start++;
            }
        }
        if (answer == N + 1) {
            System.out.println(0);
        } else {
            System.out.println(answer);
        }
    }
}