코드트리 [자바 java] 가장 짧은 부분합

https://www.codetree.ai/missions/8/problems/shortest-subtotal?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

이 문제는 배열이 주어지고 이 배열에서 연속한 합을 구했을 때 S이상인 경우중 가장 짧은 경우의 길이를 구하는 문제이다.

 

https://ethereal-coder.tistory.com/140

[알고리즘 개념] Shorten time technique

앞서, 위 글에서 설명한 적이 있는데 위 글에 있는 문제에서는 특정 수 이하에서의 최댓값을 구하라고 하였고, 이  문제에서는 특정 수 이상의 최솟값을 구하라고 하였다.

 

나는 투포인터를 사용하였다. i와 r을 이용하였고, i는 왼쪽에 있는 포인터, r은 오른쪽에 있는 포인터를 나타낸다. 이 둘을 움직이면서 sum값을 갱신한다.(sum은 i부터 r까지의 합) 

i를 기준으로 for문을 작성하고, r값을 옆으로 계속 이동한다. 만약 sum이 s값보다 크거나 같으면 break한다. 최솟값을 구해야하기 때문에 더 가는 것은 의미가 없기 때문이다. 이때의 r에서 i의 칸수가 이 답을 의미하는 ans값보다 작다면 ans값을 갱신한다.

 

이때 r-i+1이 0보다 작거나 같으면 답과 비교하지 않는다. 이 값이 0보다 작거나 같으면, 나올 수 있는 가장 최솟값인 1이 이미 나왔다는 의미이기 때문이다.(의미가 없다)

 

끝까지 탐색하면 답은 ans에 자동으로 저장되게 된다.

 

import java.io.*;
import java.util.*;
import java.math.*;

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());

        st = new StringTokenizer(br.readLine());

        int[] arr = new int[n];

        for(int i = 0;i<n;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        //투포인터 앞에서부터 차례로 탐색, 합한 값이 s가 넘으면 바로 break

       
        int r = 0;
        int ans = 1000000;
        long sum = arr[0];

        for(int i = 0;i<n;i++){

            while(true){
                if(sum >= s) break;
                if(r == n-1) break;
                r++;
                sum += arr[r];
            }

            //System.out.printf("%d %d\n", i,r);

            //System.out.println(ans);
            if(sum < s) continue;
            sum -= arr[i];
            if(r-i+1 <= 0) continue;
            ans = Math.min(ans, r-i+1);

        }
        
        if(ans == 1000000) System.out.println(-1);
        else System.out.println(ans);

    }
}