📄 문제 설명

문제

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

✍🏻 문제 풀이

적용 개념

시간 복잡도를 O(N)으로 줄이기 위해 투 포인터를 이용해서 풀었다.

투 포인터 개념

• 투 포인터는 부분합을 구할 때 유용하게 사용할 수 있는 개념인데, 배열의 시작 지점인 start와 끝 지점인 end를 명시해 합을 구하고 범위를 조절할 수 있도록 하는 방법이다.

투 포인터 적용

• start를 증가시키는 경우 : 자연수의 배열이므로, 구해야하는 합보다 현재 구간 합이 크거나 같을 경우 start를 증가시켜서 다음 합을 찾음
• end를 증가시키는 경우 : 자연수의 배열이므로, 구해야하는 합보다 현재 구간 합이 작을 경우 증가시켜서 더하는 수를 늘림

문제 적용

1. 이 문제에서는 S와 정확히 같은 경우가 아니라 S보다 크거나 같은 경우를 카운트 한다.
2. 따라서 S보다 크거나 같을 경우 구간의 길이를 재고, 다음 영역으로 옮기기 위해 start를 조정한다.
3. 어차피 길이 최소값을 구하는 거니까 S를 넘기만 하면 다음 구간으로 옮기면 됨!

💡 전체 코드

package TwoPointer;

import java.util.Scanner;

public class BOJ1806 {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int start = 0;
        int end = 0;
        int N = s.nextInt();
        int S = s.nextInt();
        //초기화
        int[] numbers = new int[N];
        for (int i = 0; i < N; i++) {
            numbers[i] = s.nextInt();
        }
        //투 포인터 돌리기
        int length = Integer.MAX_VALUE;
        while (start < N && end < N) {
            int sum = 0;
            for (int i = start; i <= end; i++) {
                sum += numbers[i];
            }
            if (sum < S) {
                end++;
            } else {
                length = Math.min(length, end - start + 1);
                start++;
                if (end < start) {
                    end++;
                }
            }
        }
        System.out.println(length);
    }
}

시간복잡도가 안맞음,, 다시 바꿨다!

package TwoPointer;

import java.util.Scanner;

public class BOJ1806 {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int start = 0;
        int end = 0;
        int N = s.nextInt();
        int S = s.nextInt();

        int[] numbers = new int[N];
        for (int i = 0; i < N; i++) {
            numbers[i] = s.nextInt();
        }

        int length = Integer.MAX_VALUE;
        int sum = 0;
        while(true){
            if (sum >= S) {
                length = Math.min(length, (end - start));
                sum -= numbers[start++];
            }
            else if (end == N) {
                break;
            }
            else {
                sum += numbers[end++];
            }
        }
        if (length == Integer.MAX_VALUE) {
            System.out.println(0);
        }
        else System.out.println(length);
    }
}