[알고리즘] 투 포인터

백준 1806

import java.io.*;
import java.util.*;

public 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[] arr = new int[n+1];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int start = 0;
		int end = 0;
		int len = Integer.MAX_VALUE;
		int sum = 0;
		while(start <= end && end <= n) {
			if(sum < s) {
				sum += arr[end++];
			} else if(sum >= s) {
				len = Math.min(len, end-start);
				sum -= arr[start++];
			}  
		}
		System.out.println(len==Integer.MAX_VALUE ? 0 : len);
	}
}

얻어갈 점

• 투 포인터를 이용한 문제 풀이 => why? 특정 구간의 합을 구하는 것! => start, end 인덱스를 사용하여 길이를 조절하여 풀면 되겠다!
• int[] arr = new int[n+1] => 처음엔 배열의 개수를 n개로 지정했다 그러나 아래의 핵심 로직 쪽에서 이 조건을 사용하여 결정하면 end<n이 된다. 즉 n-1에서 n이 되면 종료하면 된다고 생각했음.
• 그러나 해당 방식은 end가 끝까지 간 후에 , start인덱스를 하나씩 밀면서 생길 수 있는 답을 빼먹게 된다. => 따라서 n+1로 하나 더 설정하고 end가 끝나더라도 start가 따라올 수 있게 조정
• while 조건문은 start가 end를 따라가는 방식이니 start<=end로 구성하고, end<=n으로 작성(사실 여기서 start=end를 어떻게 처리할까 고민했는데 같은 것을 가리킬때 해당 인덱스의 값이 원하는 값이 나오면 그것도 정답이니 <=로 처리)
• sum>0 , sum==0 로 분리할까 sum>=0으로 할까 고민했었는데, 문제에서 원하는 값이 나오더라도 최소 길이를 구하는 것이니 >=로 묶어주고 지속적으로 len을 비교하는 로직으로 구성
• Math.min()함수는 파라미터로 온 값들 중 최소를 뱉어줌