백준 부분합 1806 java

문제링크

문제 접근

• 구간합 배열을 만들자
• 이중 포문 돌면 시간초과 난다
• 반복문 하나로 끝내야 한다

코드

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

public class baek_1806 {
    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[] nums = new int[N+1];
        int[] numSum = new int[N+1];
        st = new StringTokenizer(br.readLine());
        int temp = 0;
        for(int i=1;i<=N;i++){
            int nowNum = Integer.parseInt(st.nextToken());
            nums[i] = nowNum;
            temp += nowNum;
            numSum[i] = temp;
            if(nowNum >= S){
                System.out.println(1);
                return;
            }
        }
        if(temp < S){
            System.out.println(0);
            return;
        }
        int answer = Integer.MAX_VALUE;
        int left = 1;
        int right = 2;
        while(right <= N && left <= N && left < right){
            int sum = numSum[right] - numSum[left - 1];
            if(sum >= S){
                answer = Math.min(answer, right - left + 1);
                left++;
            }
            else right++;
        }
        System.out.println(answer == Integer.MAX_VALUE ? 0 : answer);
//        for(int i=2;i<=N;i++){
//            for(int end=0;end<N;end++){
//                int start = end - i;
//                int sum;
//                if(start < 0) continue;
//                else if(start == -1)sum = numSum[end];
//                else sum = numSum[end] - numSum[start];
//
//                if (sum >= S) {
//                    System.out.println(i);
//                    return;
//                }
//            }
//        }
//        System.out.println(0);
    }
}

결과

정리

• 주석 코드가 이중포문 코드
• 인덱스를 두 개 만들어서 반복문 하나로 끝낸다