백준 1806번: 부분합 [투포인터][누적합][구간합] - Java

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

1806번: 부분합

투 포인터의 기본적인 문제.

문제를 잘 읽어야 한다는 교훈을 얻었다. S 이상이 되는 것...... S == sum라고 읽어버려서... 계속 틀렸다고나옴 ㅠ

 

시간 복잡도는 O(N)

 

<Java 코드>

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

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		//System.setIn(new FileInputStream("Test.txt"));
		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];
		int hap[] = new int[N];

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

			// 누적합
			if (i == 0)
				hap[0] = arr[0];
			else
				hap[i] = hap[i - 1] + arr[i];

		}

		// 투 포인터 생성
		int idx1 = 0;
		int idx2 = 0;

		// 가장 최소의 길이
		int res = 100001;
		int sum = 0;
		
		while (idx1 < N && idx2 < N ) {
//			System.out.println("idx1 = "+ idx1+" , idx2 = "+ idx2);
			sum = hap[idx2] - hap[idx1] + arr[idx1];
			
			if (sum >= S) {
				res = Math.min(res, idx2 - idx1 + 1);
				idx1 ++; //더 더해봤자 더 큰수만 나올뿐..
				if(idx1 > idx2)
					idx2=idx1;
			} else {
				idx2 ++; //다음 차례 인덱스도 더해서 S가 되는지 확인해봐야지!
			}

		}
		
		if(res > 100000)
			res= 0;
		System.out.println(res);

	}

}