[백준]1806번 부분합

풀이생각

• [ 연속된 수들의 부분합 ] ! 이라는 것에서 Sliding Window나 Two pointer를 사용할 것을 생각해 볼 수 있다.
• 그 합이 [ S 이상 ] 인 것 중, [ 가장 짧은 것 ]의 길이를 구하라.
• 나에게 더 익숙한 Sliding Window방식을 사용 - 증가시키다가, S를 넘는순간 길이를 update && 맨 첫 번째 원소를 제외시킨다.
  • 즉 fixed size Window가 아닌, 화장,축소하는 window를 가진 sliding window기법을 사용한다.
  • 따라서 O(n)의 시간이 걸릴 것으로 예상된다.

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

public class Main {
    public static int min=Integer.MAX_VALUE;
    public static int n,s;
    public static int[] arr = new int[100000];
    public static void solve(){
        int windStart =0,windEnd=0;
        int curSum=0;
        for(windEnd=0;windEnd<n;windEnd++) {
            curSum += arr[windEnd];
            if (curSum < s) continue;
            // min update
            if ((windEnd - windStart + 1) < min) {
                min = windEnd - windStart + 1;
            }
            // windStart를 빼기 시작한다.
            while (windEnd > windStart) {
                curSum -= arr[windStart];
                windStart++;
                if (curSum < s) break;
                // still curSum>=s -> min update
                if ((windEnd - windStart + 1) >= min) continue;
                min = windEnd - windStart + 1;
            }
        }
    }
    public static void Setting() 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());
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++){
            arr[i]=Integer.parseInt(st.nextToken());
        }
    }
    public static void main(String[] args) throws IOException {
        Setting();
        solve();
        if(min==Integer.MAX_VALUE)System.out.println(0);
        else System.out.println(min);
    }
}

다른 풀이로는 —> 투 포인터

• 사실 위의 Sliding Window도 일종의 투포인터 기법이다.
• 변수만 봐도 그렇다 .WindStart와 WindEnd라는 포인터를 이용하여 풀어나가기 때문이다.
• 다만 이를 Sliding Window로 생각하게 된다면, [ 연속된 Window ] 의 start, end가 되는 것이고, 이를 Two pointer로 본다면, 문제 중에서 [연속됨] 이라는 조건이 없는 문제도 풀기에 좋게 되는 것이다 (라고 생각한다)
• 👊👊 그런데 내가 이제까지 풀었던 투 포인터문제들은 보통 [ 양 끝을 가리키는 포인터 ]로 푸는 문제들이었기 때문에, 이 문제를 투 포인터로 풀 생각은 전혀 하지 못했었다.
  • 👊👊 이 문제는, [ 같은 곳에서 시작하는 투포인터 ]로 풀 수 있다.