[ 백준 1806 / Java ] 부분합

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

1806번: 부분합

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

예제 입력 1 복사

10 15
5 1 3 5 10 7 4 9 2 8

예제 출력 1 복사

2

 

풀이

연속된 수들의 합 중에 그 합이 S이상 되는 것 중 가장 짧은 것의 길이를 구해야 한다.

이 문제는 투 포인터로 문제를 풀었다.

 

투 포인터의 특징은 두 개의 포인터를 언제 움직여야 하는 것이다.

1. low와 high 두개의 포인터를 설정해주고

2. 수열의 합(sum)이 s에 도달하거나 s보다 크면 

2.1 low에 위치에 있는 arr[low]를 빼준고 low++를 해준다.

3. 수열의 합(sum)이 s 보다 작다면

3.1 high에 위치에 있는 arr[high]를 더해주고 high++를 해준다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int n,s;
    static int[] arr;
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        n = Integer.parseInt(st.nextToken()); // 수열의 길이
        s = Integer.parseInt(st.nextToken()); // 원하는 수들의 합
        arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        System.out.println(twoPointer(arr, s));
    }
    public static int twoPointer (int[] arr, int s) {
        int current = 0, shortest = Integer.MAX_VALUE;
        int low = 0, high = 0;
        int sum = 0;
        while (true) {
            if (sum >= s) { // sum이 s보다 크거나 같을때
                shortest = Math.min(shortest, current); //짧았던 길이를 shortest에 저장하고
                sum -= arr[low++]; //sum이 s보다 크거나 같기때문에 low 포인터 부분을 sum에서 빼고 오른쪽으로 움직여준다
                current--; // 길이도 하나 줄인다
            } else if (high == arr.length) { //arr 끝에 도달
                break;
            } else { //s 보다 작을 때는 high 포인터를 움직여 sum에 더해준다
                current++;
                sum += arr[high++];
            }
        }
        if (shortest == 2147483647) { //sum이 s보다 크거나 같은 경우가 없을 경우 0을 출력한다.
            shortest = 0;
        }
        return shortest;
    }
}