문제링크

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

구현방법

N의 범위가 최대 10만이기 때문에 O(N^2)이 도는 순간 시간제한을 넘기고 시간초과 발생 무조건 그 이하의 시간복잡도를 가져야한다.

-> 그러면 가장 적합한것은 투 포인터 알고리즘 왜냐 O(N)의 시간복잡도를 가지기 떄문에

원래 투포인터 알고리즘을 하듯이 진행해도되며 , 거기서 값을 체크할때 S이상이면서 최소길이 체크만 조심해서 체크를 진행하면 수월하게 풀수 있는 문제였습니다.

구현알고리즘

투 포인터 알고리즘

CODE

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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 check_sum = 0;
        //길이 체크용도
        int size = 0;

        //결과 출력을 위해서 최소길이 체크 용도
        int min_size = 0;

        //수열을 가지고 있을 배열
        int num_list[] = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int idx =0; idx < N;idx++){
            num_list[idx] = Integer.parseInt(st.nextToken());
        }

        int right = 0;
        int left = 0;

        while(right !=N){
            //두 포인터 중 하나가 마지막에 도착한경우
            //첫 포인터가 마지막에 도착할떄까지 체크
            if(left == N) {
                check_sum -= num_list[right++];
                size -= 1;
                if (check_sum == S) {
                    min_size = check_size(min_size, size);
                }
                continue;
            }
            //check_sum 이 S보다 크거나 같은 경우
            if(check_sum >= S){
                check_sum -= num_list[right++];
                size-=1;
            }
            //check_sum 이 S보다 작은경우
            else if(check_sum < S){
                check_sum += num_list[left++];
                size+=1;
            }
            //S이상인경우 체크
            if(check_sum >= S){
                min_size = check_size(min_size,size);
            }



        }

        System.out.println(min_size);

    }

    //최소 길이 체크용
    private static int check_size(int minSize, int size) {
        if(minSize == 0){
            return size;
        }else{
            minSize = Math.min(minSize,size);
            return minSize;
        }
    }
}