[실버4] BOJ2003 수들의 합2

요구사항 정의

• 수열 A의 부분 수열이 M이 되는 경우의 수를 출력하시오.

문제 분석

• 시간 제한 0.5초, 최대 N = 10000
  → O(N^2) 알고리즘은 위험하며 시간 복잡도가 O(N log N) 이하인 알고리즘을 사용해야 안전함.
• 부분 합, 투 포인터 → O(N)의 시간복잡도
• start와 end 투 포인터를 두고 sum과 M을 비교, 다음 세가지 조건에서만 포인터를 이동시킴

1. 현재 부분합이 M보다 큰 경우
- 부분합에서 start에 해당하는 값을 뺌
- start를 이동시킴

2. 부분합이 M보다 작은 경우 
- end를 이동시킴
- 이동했는데 N과 같아진 경우(=수열을 벗어났다) break;
- 아닌 경우, 부분합에서 end에 해당하는 값을 더함

3. 일치하는 경우
- count 증가
- 부분합에서 start 요소 빼고, start 증가
- end 증가, 부분합에서 end 더함
- 만약 end 증가시켰는데 N과 같아졌다. → 동일하게 break;

Code

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

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 M = Integer.parseInt(st.nextToken());
        int A[] = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            A[i] = Integer.parseInt(st.nextToken());
        }
        //데이터 처리 완료

        int s_index = 0;
        int e_index = 0;
        int sum = A[0];
        int count = 0;

        while(e_index < N) {
            if(sum < M) { // 현재 부분합이 목표보다 작은 경우
                e_index++;
                if(e_index < N) {
                    sum += A[e_index];
                } else {
                    break;
                }
            } else if(sum > M) { // 현재 부분 합이 목표보다 큰 경우
                sum -= A[s_index];
                s_index++;
            } else { // 일치하는 경우
                count++;
                sum -= A[s_index];
                s_index++;
                e_index++;
                if(e_index < N) {
                    sum += A[e_index];
                } else {
                    break;
                }
            }
        }
        System.out.println(count);

    }
}