[백준 Java] 1806번 부분합

💡문제

[Gold IV] 부분합 - 1806

문제 링크

성능 요약

메모리: 22768 KB, 시간: 216 ms

---

🤔접근법

구간합이 S 이상이 되는 것 중 구간이 가장 짧을 때의 길이를 출력하는 문제

범위 체크 및 시간복잡도 예상

• 10 ≤ N ≤ 100,000
• 0 ≤ S ≤ 100,000,000
• 1 ≤ 원소의 값 ≤ 10,000
• $O(N)$이하 가능하다.

풀이법

❌ 접근 방법. 완탐

1. 수열의 시작점을 탐색→ $O(N)$
2. 시작점으로 부터 합이 S가 되는 끝점 찾기→ $O(N)$

➡️ 해당 풀이법의 시간 복잡도 : $O(N^2)$ → 시간 초과

⭕ 접근 방법. 투포인터, 슬라이딩 윈도

1. 수열에서 연속한 부분수열의 구간을 보는데 start = 0, end = 0으로 두고 시작
2. 구간을 늘려가면서 구간 내에 합이 S 이상인지 확인
   1. 크거나 같다면 가장 짧은 길이인지 확인 후 갱신
   2. 만약 구간내에 합이 S보다 작으면 end를 증가시켜 구간을 늘린다.
   3. 합이 크거나 같다면 새로운 구간을 보기 위해서 start를 증가 후 반복→ $O(N)$
      시작점를 증가시켰으니 구간에서 제외된 정수를 합에서 빼어 구간합을 정정해주어야한다.

➡️ 해당 풀이법의 시간 복잡도 : $O(N)$

---

😎SUCCESS

고냥 담박에 성공

---

👩‍💻 코드

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

public class Main_1806_2 {
    static int N; // 배열의 요소 개수
    static int S; // 부분 배열의 합이 될 목표 값
    static int arr[]; // 입력 정수를 저장하는 배열
    static int min = Integer.MAX_VALUE; // 최소 길이를 저장하는 변수

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // N과 S를 입력으로 받음
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());

        // 배열 요소를 입력으로 받음
        st = new StringTokenizer(br.readLine());
        arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int start = 0; // 현재 부분 배열의 시작 인덱스
        int end = 0;   // 현재 부분 배열의 끝 인덱스
        int sum = arr[end]; // 현재 부분 배열의 합

        while (end < N) {
            // 현재 부분 배열의 합이 목표 값 이상인 경우 최소 길이 갱신
            if (sum >= S) {
                min = Math.min(min, end - start + 1);
            }

            // 부분 배열의 합이 목표 값 미만이면 end를 증가시켜 합에 새로운 요소 추가
            if (sum < S) {
                end++;
                if (end < N) {
                    sum += arr[end];
                }
            } else { // 부분 배열의 합이 목표 값 이상이면 start를 증가시켜 합에서 요소 제거
                sum -= arr[start];
                start++;
            }
        }

        // 최소 길이 출력 (최소 길이가 초기값 그대로이면 부분 배열을 만들 수 없으므로 0 출력)
        System.out.println(min == Integer.MAX_VALUE ? 0 : min);
    }
}