백준 1806 부분합 - 투 포인터

투 포인터인지 문제를 보자마자 알진 못했다. 이것도 실전에서는 여러 알고리즘을 하나씩 가능한지 확인해보고 사용하게 될 것 같다.

투 포인터 풀이법

1. left right를 0으로 초기화한다
2. left가 범위를 넘어가지 않을때 까지 반복
3. 조건을 충족하면 left ++
4. 조건을 충족하지 못하면 right ++
5. right가 범위를 넘어가면 left++

public static void main(String[] args) throws IOException {

        String[] inp = br.readLine().split(" ");
        int n = Integer.parseInt(inp[0]);
        int s = Integer.parseInt(inp[1]);

        inp = br.readLine().split(" ");
        int[] stackSum = new int[n+1];

        for (int i = 0; i < n; i++) {
            stackSum[i+1] = stackSum[i] + Integer.parseInt(inp[i]);
        }

        int left=0;
        int right =0;

        int ans = Integer.MAX_VALUE;
        while (left <= n){
            // right 는 n+1이 되면 안돼

            int dif = stackSum[right] - stackSum[left];
            if (dif >= s){
                ans = Math.min(ans, right-left);
                left ++;
            }
            else{
                if (right < n){
                    right++;
                }
                else{
                    left ++;
                }
            }
        }

        if (ans == Integer.MAX_VALUE){
            System.out.println(0);
        }
        else {
            System.out.println(ans);
        }
    }