투 포인터 - BOJ - 1806 부분합

문제

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

1806번: 부분합

 

 

 

문제 접근

• 앞서 해보았던 투 포인터 유형의 대표적인 문제인 부분합 / 구간 찾기 문제이다.
• 문제를 상세히 읽어보면 부분합이 S이상이 되면 되므로 $S_{cur} \geq S_{target}$ 를 만족하게 되면 left를 하나씩 올리면서 위 구간합이 만족하는지를 검사하며 구간을 줄여나가면 된다.
• 만약 $S_{cur} < S_{target}$ 라면 right를 움직여서 다음 요소를 더하도록 하면 된다. 이상이라는 말에 주목하면 나머지는 투 포인터 구현의 기본적인 문제였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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[] data = new int[N];

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

        for (int i = 0; i < N; i++){
            data[i] = Integer.parseInt(st.nextToken());
        }

        int ans = 100000;
        int start = 0;
        int end = 0;
        int sum = 0;

        while(true){
            if (sum >= S){
                int distance = end - start;
                ans = Math.min(ans, distance);
                sum -= data[start++];
            } else if (end == N){
                break;
            } else {
                sum += data[end++];
            }
        }

        if (ans == 100000){
            System.out.println(0);
        } else{
            System.out.println(ans);
        }
    }
}

• 구현하면서 느꼈던건 end의 경우, 순서를 잘못하면 ArrayOutOfBounds 가 뜰 수 있다. 반드시 end의 길이 체크를 끝낸 뒤에 end를 올리도록 하는게 중요하단 것이었다.