🔗 Problem

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

👩‍💻 Code

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

// 부분 합

public class BJ1806 {
	
	static int n;
	static int s;
	static int[] arr;
	static int length = Integer.MAX_VALUE;
	static int start;
	static int end;
	static int total;
	
	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];
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < arr.length; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		while(true) {
			
			if(total >= s){
				length = Math.min(length, end - start);
				total -= arr[start];
				start++;
			}
			else if(end == n) break;
			else {
				total += arr[end];
				end++;
			}	
		}
		
		if(length == Integer.MAX_VALUE) length = 0;
		System.out.println(length);
	}
	
}

💡 Learned

아이디어

• Two-pointer 알고리즘을 공부한 후 풀었다.

Two-pointer

• 일차원 배열 위에서 두 포인터 start와 end를 움직이며 원하는 결과를 얻는 알고리즘
• 문제에 따라 두 포인터가 같은 방향 또는 반대 방향으로 움직이도록 구현한다.
• 각 포인터가 n번 누적 증가해야 알고리즘 종료
• O(2N) -> 시간복잡도는 O(N)