JAVA 백준 1806 부분합 (두 포인터, 누적합)

 

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

 

---

문제

1. 첫째 줄에 N ( 10 <= N <= 100000 ) 과 S ( 0 <= S <= 100000000 ) 을 공백으로 구분하여 입력.
2. 둘째 줄에 수열에 들어갈 수 N개를 공백으로 구분하여 입력.
3. 수열의 수 중 합이 S 이상이 되는 것 중 가장 짧은 것의 길이를 출력.

---

 

누적합을 이용하여 모든 수의 누적합 배열을 만든 후 그 배열을 돌아가며 길이를 구하는 방식.

 

left, right 두 개의 포인터를 같은 방향으로 움직이면서 right가 가리키고 있는 누적합 배열의 수에서 left가 가리키는 누적합 배열의 수를 뺐을 때 S가 넘으면 left를 증가하면서 길이가 최소가 되면서 합이 S 이상이 되도록 만드는 길이를 찾아 출력

 

 

최종 코드

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

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 min = 100001;

        int[] sum = new int[N];
        int temp = 0;

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

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());
            temp += num;
            sum[i] = temp;
            if (num == S) {
                min = 1;
            }
        }

        int left = 0;
        int right = 1;

        if (min != 1) {
            while (left < right && right <= N - 1) {
                if (sum[right] >= S) {
                    if (min > right - left + 1) {
                        min = right - left + 1;
                    }

                    while (left < right && sum[right] - sum[left] >= S) {
                        if (min > right - left) {
                            min = right - left;
                        }
                        left++;
                    }

                    right++;
                } else {
                    right++;
                }
            }
        }

        if (min == 100001) {
            System.out.println(0);
        } else {
            System.out.println(min);
        }
    }
}