[백준] 1806 부분합 풀이 java

1. 문제 설명

문제 설명

2. 접근 방식

KEY WORD: 구간합 & 투 포인터

데이터 크기가 10^5 이라서 시간복잡도가 O(n^2) 이상이면 안된다. 따라서 한번의 조회안에 모든 것을 끝내야 한다. 그러기 위해서 누적합을 사용하여 문제를 풀었다. 진행 방식은 다음과 같다.

1. 입력을 누적합 배열(sum) 형태로 만든다. (다만 진짜 누적합의 시작은 sum[1] 부터 시작하고, sum[0]=0 으로 비워둔다.)
2. left, right 포인터를 만들고 다음과 같이 움직인다.
   (1) sum[right] - sum[left] < M 이면 right를 움직인다.
   (2) sum[right] - sum[left] == M 이면 (right-left) 길이 기록 후에, right를 움직인다.
   (3) sum[right] - sum[left] > M 이면 (right - left) 길이 기록 후에 left를 움직인다.

🤔 sum[right] - sum[left] > M 인데 left를 ++ 하는 이유

구간합이 M 이상인 경우 중 길이가 제일 짧은 경우의 수의 길이를 출력해야 한다. sum[right] - sum[left] > M 인 값을 현재 만났는데, 또 right++ 을 해버리면 이미 충족한 M 이상이란 요건에서 길이는 더 길어지기에 쓸모 없다.
따라서 sum[right] - sum[left] > M 이면 길이 기록 후, left를 올려서, 칸 수를 줄인다.

M으로 맞아 떨어지지 않을 수 있기 떄문에 sum[right] - sum[left] > M인 경우도 세어야 한다.

3. 코드 분석

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

public class Main {
    // 구간 합 + 투 포인터
    // 전 구역의 누적합을 구한다.
    // sum[right] - sum[left] 와 target 값을 비교해서, right나 left를 이동 시킨다.
    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 M = Integer.parseInt(st.nextToken());
        long [] sum = new long [N+1];
        // 1. 누적합 만들기
        st = new StringTokenizer(br.readLine());
        sum[0] = 0;
        sum[1] = Integer.parseInt(st.nextToken());
        for (int i = 2; i <= N; i++) {
            sum[i] = sum[i-1] + Integer.parseInt(st.nextToken());
        }
        // 2. 투포인터로 값 구하기
        int left = 0, right = 0;
        long cur_sum = 0;
        long cur_len = Integer.MAX_VALUE;
        while (right <= N){
            cur_sum = sum[right] - sum[left];
            if(cur_sum == M){
                cur_len = Math.min(cur_len, right -left);
                right++;
            } else if (cur_sum < M) {
                right++;
            } else {
                cur_len = Math.min(cur_len, right -left);
                left++;
            }
        }
        System.out.println(cur_len == Integer.MAX_VALUE? 0 : cur_len);
    }
}