[Java] 백준 1806 부분합

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

난이도

골드4

문제

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

입력

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

출력

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

내 코드

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

class Main {
	public static void main(String[] args) throws IOException {
		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[] nums = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}

		int left = 0, right = 0, sum = 0, ans = Integer.MAX_VALUE;

		while (true) {
			if (sum >= S) {
				ans = Math.min(ans, right - left);
				sum -= nums[left];
				left++;
			} else {
				if (right == N) {
					break;
				}
				sum += nums[right];
				right++;
			}
		}
		System.out.println(ans != Integer.MAX_VALUE ? ans : 0);
	}
}

투 포인터 문제였다.

sum >= S인 경우
현재 구간의 길이(right - left)를 업데이트하며 최소값을 갱신한다.
왼쪽 포인터(left)를 증가시키고, sum에서 nums[left]를 빼며 구간을 축소한다.

sum < S인 경우
오른쪽 포인터(right)를 이동시키며 sum에 nums[right]를 더한다.

while문 종료 조건
right == N일 때, 모든 경우를 탐색했다는 의미로 while문 종료한다.