[백준] 1806 부분합 (Java) [투포인터]

문제

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

1806번: 부분합

 

알고리즘

투포인터

 

풀이

1. start, end 위치 각각 정의

2. 합이 S이상 인 경우 현재까지 더한 sum에서 start 위치에 있는 값을 빼주고 start++ 처리한다.

또한, 합이 S이상인 경우일 때 최소 길이를 구해야 하기 떄문에 최소 길이를 구하는 로직도 포함시킨다.

3. 합이 S미만 인 경우 end 위치에 있는 값를 더하고 end++ 처리한다.

4. 최소 길이 출력 (없으면 0출력)

 

코드

package com.company;

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

public class Test_TwoPointer {
    static int N, S;
    static final int INF = 1000000001;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());

        int[] arr = new int[N];
        st = new StringTokenizer(bf.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int startIdx = 0;
        int endIdx = 0;
        int sum = 0;
        int ans = INF;
        while (startIdx < N) {
            if (sum >= S) { //합이 S이상인 경우
                ans = Math.min(ans, endIdx - startIdx);
                sum -= arr[startIdx];
                startIdx++;
            } else if(endIdx == N){ //S이상을 더이상 만들 수 없는 경우 endIdx가 N에 도달
                break;
            }
            else { //합이 S 미만인 경우
                sum += arr[endIdx];
                endIdx++;
            }
        }

        if (ans == INF) { //합을 만드는 것이 불가능한 경우
            System.out.println(0);
        } else {
            System.out.println(ans);
        }
    }
}