Computer Science/알고리즘

백준 Java | BOJ #1806 부분합

토마토. 2023. 1. 31. 14:32
package DAY02.P1806;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Main {
    public static int N;
    public static int S;
    public static int[] array;

    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream("src/DAY02/P1806/input.txt"));
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        S = scanner.nextInt();
        array = new int[N];
        for (int i=0;i<N;i++){
            array[i] = scanner.nextInt();
        }

        int left = 0;
        int right = 0;
        int min_length = Integer.MAX_VALUE;
        int sum = array[0];

        while (right < N){
            //print(left, right);
            //System.out.println(sum);
            //System.out.println(min_length);
            if (sum < S){
                //System.out.println("sum is smaller than S");
                if (right == N-1){
                    break;
                } else {
                    right++;
                    sum += array[right];
                }
            } else {
                //System.out.println(right-left+1);
                if (left <= right){
                    int tmp_length = right - left + 1;
                    //System.out.println("tmp_length" + tmp_length);
                    if (min_length > tmp_length){
                        min_length = tmp_length;
                    }
                    if (left == right){
                        if (right == N-1){
                            break;
                        } else {
                            right++;
                            sum += array[right];
                        }
                    } else {
                        sum -= array[left];
                        left++;
                    }
                } else {
                    left = right;
                }
            }
        }
        if (min_length == Integer.MAX_VALUE){
            System.out.println(0);
        } else {
            System.out.println(min_length);
        }
    }
    public static void print(int left, int right){
        for (int i=0;i<N;i++){
            if (left==i){
                System.out.print(" L" + array[i] + "L ");
            } else if (right==i){
                System.out.print(" R" + array[i] + "R ");
            } else {
                System.out.print(" " + array[i] + " ");
            }
        }
        System.out.println();
    }
}