[Java] 백준 1806. 부분합

문제 

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

1806번: 부분합

주어진 배열의 연속된 subarray 에서 subarray.sum() <=  tartget 을만족하는 minLen(subarray) 를 구하는 문제.

알아야 할 개념

• 투포인터 sum

 

풀이

윈도우 슬라이드를 만들어 투포인터 탐색으로 sum을 check하면서 정답을 리턴하는 문제.

 

풀이 알고리즘은 다음과 같다.

1. 주어진 배열을 누적합하여 저장한다.
2. 투포인터 left, Right로 배열을 O(L + R ) 탐색한다.
   1. from L to R 까지의 연속 부분합이 S 보다 클때까지 R 포인터를 오른쪽 이동한다.
   2. from L to R 연속 부분합이 S보다 작아질때까지 L 포인터를 오른쪽 이동한다
   3. 최소 len을 갱신한다.
3. 정답을 리턴한다.

이 문제는 전형적인 투 포인터 알고리즘 이다.(웰노운)

 

코드

자바

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

public class Main {

    public static void main(String[] args) throws IOException {
        Main m = new Main();
        System.out.println(m.solution());
    }
    public long solution() throws IOException {
        FastReader fr = new FastReader();
        int N , S;
        N = fr.nextInt();
        S = fr.nextInt();
        long arr[] = new long[N+1];
        for(int i =1 ;i <= N ;i++){
            arr[i] = fr.nextInt();
        }
        //for two-pointer , convert arr elmenets
        for(int i = 1 ;i <= N ;i++)arr[i] += arr[i-1];
        //System.out.println(arr[N] + ", "+S);
        if(arr[N] < S)return 0;
        int L = 0;
        int R = 0;
        long minLen = Long.MAX_VALUE;
        while(R < arr.length && L < arr.length){
            if(arr[R]-arr[L] < S){
                R++;
            }else{
                while(L<=R && arr[R]-arr[L] >=S){
                    minLen = Math.min(minLen, R-L);
                    L++;
                }
            }
        }
        return minLen == Long.MAX_VALUE ? 0 : minLen;
    }
    public static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}