[백준] 1806번 : 부분합[Java]

#풀이

이진탐색 풀이

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[] nums = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<N; i++){
            nums[i] = Integer.parseInt(st.nextToken());
        }
        int left = 1;
        int right = N;
        int ans = 0;
        while(left<=right){
            boolean flag = false;
            int mid = (left+right)/2;
            int sum = 0;
            for(int i = 0; i<mid; i++ ){
                sum+=nums[i]; // 초기 세팅
            }
            if(sum>=S){
                right = mid-1;
                ans = mid;
                continue;
            }
            for(int i = 1; i<N-mid+1; i++ ){
                sum-=nums[i-1];
                sum+=nums[i+mid-1];
                if(sum>=S){
                    flag = true;
                    right = mid-1;
                    ans = mid;
                    break;
                }
            }
            if(!flag)left = mid+1;

        }

        System.out.println(ans);
    }

}

투 포인터 풀이

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[] nums = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<N; i++){
            nums[i] = Integer.parseInt(st.nextToken());
        }
        int left = 0;
        int right = 0;
        int ans = Integer.MAX_VALUE;
        int sum = 0;
        while(true){
            if(sum>=S){
                sum-=nums[left];
                ans = Math.min(ans,right-left);
                left++;
            }
            else if (right == N)         
                break;
            else{
                sum+=nums[right++];
            }
        }
        if(ans==Integer.MAX_VALUE)ans = 0;
        System.out.println(ans);
    }

}

#성능

이분탐색

 

투포인터

#정리

이 문제는 두가지 방법으로 풀 수 있다.

1. 이분탐색+슬라이딩 윈도우 -> 이분탐색으로 최소길이를 찾는다. 해당 길이에서 S보다 큰 부분합이 있는지 슬라이딩 윈도우로 확인한다. 이 경우 시간복잡도는 O(NlogN)이다.

2. 투 포인터로 모든 부분 합에 대해 S와 비교한다. 이 경우 시간복잡도는 O(N)이다.