[JAVA] 백준 1806- 부분합

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

1806번: 부분합

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
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 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 sum = 0, left = 0, cnt = 0, answer = Integer.MAX_VALUE;
        boolean exist = false;
        for(int right = 0; right<n; right++){
            sum+=arr[right]; // right 인덱스를 증가시키며 sum에 누적
            cnt++;

            while(sum >= s) { // 합이 s이상이면
                exist = true;
                answer = Math.min(answer, cnt); // 최소 길이 갱신
                sum -= arr[left++]; // left 인덱스를 증가시키며 그 값을 빼줌
                cnt--;
            }
        }
        System.out.println(exist ? answer : 0);
    }
}

 

 

n의 범위가 10만이므로 O(n^)으로 풀면 안된다.

투포인터 알고리즘을 사용해 O(n)으로 줄이도록 한다.