백준 1806 JAVA : 부분합

문제

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

1806번: 부분합

 

풀이 예상

투포인터를 이용해서 startPoint와 endPoint의 차이로 길이를 구한다.

 

풀이방법 (접근 방법 & 시간복잡도)

1. startPoint를 0부터 N까지 늘려간다.

2. 합이 S이상일 때 까지 endPoint를 증가시켜서 sum에 더해준다.

3. startPoint 값을 sum에서 빼준다.

 

 

예제를 예시로 들어보면,

10 15
5 1 3 5 10 7 4 9 2 8

 

1. 초기 세팅

startPoint, endPoint = 0, sum = 5(nums[0])

 

2. startPoint = 0

합이 15 이상일때 까지 end Point를 증가시키면 endPoint =  4, sum = 24 가된다.

endPoint - startPoint+1 이 부분합의 길이 이므로 값을 갱신시킨다.

startPoint의 값을 sum 에서 빼준다. sum = 17

 

3. startPoint = 1

이미 합이 S(15)를 넘으므로 endPoint의 증가는 없다.

answer 값을 갱신시킨다.

startPoint의 값을 sum 에서 빼준다. sum =16

 

...

 

위의 로직대로 코드를 짜면 아래와 같다

 

 

시간복잡도 => O(N)

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception{
        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 endPoint = 0;
        int sum = nums[0];
        int answer = Integer.MAX_VALUE;

        for (int startPoint = 0; startPoint < N; startPoint++) {
            while(endPoint < N && sum < S) {
                endPoint++;
                if(endPoint!=N) {
                    sum += nums[endPoint];
                }
            }
            if(endPoint == N) break;
            if(startPoint<=endPoint) {
                answer = Math.min(answer, endPoint-startPoint+1);
            }
            sum -= nums[startPoint];
        }
        
        System.out.println(answer == Integer.MAX_VALUE? 0 : answer);

    }
}

 

결과