[백준] 1806번 부분합 (투포인터, 슬라이딩 윈도우) - JAVA

🧐 문제

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

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

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

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

<예제>
10 15
5 1 3 5 10 7 4 9 2 8

---

🔸완전탐색? →🚨시간초과

주어진 수열에서 연속된 부분 수열의 합이 S 이상이 되는 가장 짧은 길이를 구하는 문제이다.
이걸 처음 접하면 for문을 중첩해서 사용하는 방식이 제일 먼저 떠오를 것이다.

int minLength = Integer.MAX_VALUE;
for (int i = 0; i < N; i++) {
    int sum = 0;
    for (int j = i; j < N; j++) {
        sum += arr[j];
        if (sum >= S) {
            minLength = Math.min(minLength, j - i + 1);
            break;
        }
    }
}

하지만 이렇게 실행시키면 시간초과로 인해 문제를 틀리게 될 것이다.

 

문제의 조건문을 다시 살펴보면 for문을 도는 횟수는 다음과 같을 것이다.

• 바깥 반복문: 최대 100,000번
• 안쪽 반복문: 평균 50,000번 → 최악의 경우엔 거의 N번씩 반복

그러면 시간복잡도는 최악의 경우 100,000 × 100,000 = 10,000,000,000 (100억) 이 되므로, 시간초과가 되는 것이다.

 

따라서 위와 같은 문제는 투 포인터(슬라이딩 윈도우) 방식을 사용해야한다.

---

🔸투 포인터 풀이 방식

투 포인터: 1차원 배열에서 각자 다른 원소를 가리키는 2개의 포인터를 활용하여 목표값을 구해나가는 방식이다.

이 방식은 하나의 반복문 내에서 조건에 따라 두 포인터를 각각 움직이며 문제를 해결하기 때문에, 일반적으로 시간 복잡도는 O(N)으로 매우 효율적이다.

 

투포인터가 효과적인 경우는 다음과 같다.

• 연속된 구간의 원소들을 처리해야 할 때
• 정렬된 배열에서 조건을 만족하는 쌍이나 부분합 등을 찾을 때

투포인터의 방식으로 위의 문제를 풀고자 한다.

---

1️⃣ 조건문 설정하기

위와 같은 배열이 있다고 가정했을 때, 두 개의 포인터를 통해서 S=15 이상인 경우를 찾고자 한다.

 

left와 right의 index를 설정하는 방식에는 크게 두 가지가 있다.

• left, right 둘 다 index 0부터 시작하면서 탐색
• left는 index 0, right는 index end로 설정하면서 탐색 ~> 이분탐색

보통 연속성을 따져야하는 경우에는 left와 right의 index를 0으로 두면서 탐색을 시도한다.

위와 같은 문제에서도 크게 바라보면 a~b의 구간 중 최소 구간을 찾는 것이므로 전자에 해당하는 문제이다.

따라서 left와 right의 index를 0으로 설정해야한다.

 

그렇다면 다음으로 고려해야할 부분은 어떤 경우에 left와 right의 index를 조정할 것인가에 대한 문제이다. 

보통 둘 다 index를 0부터 시작하는 경우에는 다음과 같이 조건을 설정한다.

1. S > sum : right ++
2. S < sum : left ++
3. S = sum : 조건 처리 -> left ++

 

하지만 위의 문제인 경우에는 S=15 이상인 구간을 구하는 게 목적이므로 다음과 같이 조건을 변형시킬 수 있다.

1. S > sum : right ++
2. S <= sum : 조건 처리 -> left ++

위와 같이 조건을 설정하였으므로 이제 정확한 동작원리를 그림을 통해 이해하고자 한다.

---

2️⃣ 투포인터 동작 원리

그림을 통해 left와 right의 포인터 변화를 살펴보고자 한다.

 

위와 같이 left와 right의 포인터가 설정되었을 때 최소의 구간이 나오게 된다. 이후의 과정을 생략하겠다.

(그 이후로도 위와 같은 과정이 반복되며 최소 구간을 계속해서 찾을 것이다..)

---

3️⃣ 조건문 코드 구현

while (true) {
    if (sum >= S) {
        minLength = Math.min(minLength, right - left); // 최소 구간 갱신
        sum -= arr[left++];
    } else if (right == N) {
        break;
    } else { // sum < S
        sum += arr[right++];
    }
}

위의 동작과정을 코드로 나타내면 다음과 같다.

• sum >= s : 최소구간을 계속해서 갱신한다, left 포인터를 움직이므로 전에 있었던 값을 뺀다
• right == N: 탈출 조건
• else : sum < S의 상황으로, sum에 증가된 right index의 값을 더해준다.

---

🔸전체 코드

// 1806 부분합
public class Main {
    public static void main(String[] args) throws Exception {
        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[] arr = new int[N];

        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i ++){
            arr[i] = Integer.parseInt(st2.nextToken());
        }

        int left = 0;
        int right = 0;
        int sum = 0;
        int minLength = Integer.MAX_VALUE;

        while (true) {
            if (sum >= S) {
                minLength = Math.min(minLength, right - left); // 최소 구간 갱신
                sum -= arr[left++];
            } else if (right == N) {
                break;
            } else { // sum < S
                sum += arr[right++];
            }
        }
        if (minLength == Integer.MAX_VALUE){
            System.out.println(0);
        }else{
            System.out.println(minLength);
        }
    }
}