[Java] 백준 BOJ / 1806번: 부분합

부분합

문제

---

문제 설명

수열이 주어지고 수열의 연속 합이 입력에서 주어지는 S 이상이 되는 최소의 길이를 구하는 문제이다.

일단 문제에서 부분합이라고 했으니 부분합을 구해주고 2중 for 문으로 문제를 풀려고 했다.

---

첫번째 구현

문제에서 주어지는 기본 배열을 저장할 arr 배열과 누적합을 구해줄 prefixSum이라는 배열을 두고 계산을 해주었다.

for (int i = 1; i <= n; i++) {
	arr[i] = Integer.parseInt(st.nextToken());
	prefixSum[i] = prefixSum[i - 1] + arr[i];
}

그리고 prefixSum에서 2중 for문으로 만약에 합이 S 이상이면 min변수를 초기화 해주는 방법으로 구현했다.

for (int i = 0; i <= n; i++) {
	for (int j = i + 1; j <= n; j++) {
		if (prefixSum[j] - prefixSum[i] >= s) {
			if (min > (j - i)) {
				min = j - i;
			}
		}
	}
}

이렇게 하니깐 시간초과가 났다.

문제에서의 N의 범위는 10 ≤ N < 100,000 였기 때문에 최대로 돌았을 경우 10,000,000,000 가지의 경우가 나오기 때문에 0.5초의 시간안에 나올 수 없었다.

그래서 투포인터 로 풀기로 했다.

---

두번째 구현

투포인터는 말 그대로 포인터를 2개를 사용해서 각 포인터를 상황에 맞게 조금씩 이동하면서 푸는 방법이다.

왼쪽 기준을 담당할 start 변수를 0으로, 오른쪽 기준을 담당할 end 변수를 1로 설정한다.

그리고 prefixSum[end] - prefixSum[start]로 sum을 구하고 비교하는 과정을 거친다.

• sum이 S값 이상이고 min이 end - start 값보다 작다면 min을 end - start로 초기화
• sum이 S값 이상이고 start가 end보다 작다면 더 짧은게 있을 수 있으니 start++
• sum이 S값 미만이거나 start가 end와 같다면 다음 경우를 탐색하기 위해 end++

위의 과정을 거쳐서 min을 구하면 된다.

start = 0;
end = 1;

while (end <= n && start <= n) {
	int sum = prefixSum[end] - prefixSum[start];
	if (sum >= s && min > end - start) {
		min = end - start;
	}
	
    if (sum >= s && start < end) {
		start++;
	}
            
	if (sum < s || start == end) {
		end++;
	}
}

이렇게 구현한 후 제출을 했는데 틀렸는데 불가능한 경우를 생각하지 않아서 틀렸다.

그래서 해당 경우를 만약에 min 값이 초기에 설정한 Integer.MAX_VALUE라면 0을 출력하게 바꿔줬다.

---

코드

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

public class Main_1806 {
    static int n, s;
    static int[] arr;
    static int[] prefixSum;
    static int min = Integer.MAX_VALUE;
    static int start, end;
    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 + 1];
        prefixSum = new int[n + 1];

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

        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            prefixSum[i] = prefixSum[i - 1] + arr[i];
        }

        start = 0;
        end = 1;

        while (end <= n && start <= n) {
            int sum = prefixSum[end] - prefixSum[start];
            if (sum >= s && min > end - start) {
                min = end - start;
            }
            if (sum >= s && start < end) {
                start++;
            }
            if (sum < s || start == end) {
                end++;
            }
        }
        if (min == Integer.MAX_VALUE) {
            System.out.println(0);
        }
        else System.out.println(min);
    }
}