백준 1806번 부분합 - Java 투 포인터

부분합

 

 

 

수열이 주어지고, 연속된 수들의 합이 S보다 크며, 크기가 가장 작은 수열의 길이를 찾는 문제이다.

누적합과 슬라이딩 윈도우(투 포인터) 로 풀이가 가능할듯 했다.

 

나는 투 포인터로 풀었다.

시작점부터 더해가면서 S보다 크다면 조건을 거쳐 가장 앞을 하나씩 지워주는 방식으로 진행했다.

 

누적합의 경우 누적합 배열을 만들어주고, 이분 탐색으로 범위를 좁히면 될것 같다.

 

🔽 투 포인터 풀이

 

import java.io.*;
import java.util.*;
 
public class Main { // 부분합
    public static int N, S;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        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 minLength = Integer.MAX_VALUE;
        int sum = 0;
        int start = 0;
 
        for (int end = 0; end < N; end++) {
            sum += arr[end];
            
            while (sum >= S) {
                minLength = Math.min(minLength, end - start + 1);
                sum -= arr[start];
                start++;
            }
        }
 
        if (minLength == Integer.MAX_VALUE) {
            System.out.println(0);
        } else {
            System.out.println(minLength);
        }
    }
}