[복합적 문제] 연속 부분 수열

 

 

 

설명

N개의 수로 이루어진 수열이 주어집니다.
이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요.

만약 N=8, M=6이고 수열이 다음과 같다면

1 2 1 3 1 1 1 2

합이 6이 되는 연속부분수열은 {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}로 총 3가지입니다.

 

 

 

입력

첫째 줄에 N(1≤N≤100,000), M(1≤M≤100,000,000)이 주어진다.
수열의 원소값은 1,000을 넘지 않는 자연수이다.

 

 

 

출력

첫째 줄에 경우의 수를 출력한다.

 

 

 

예시 입력1

8 6
1 2 1 3 1 1 1 2

 

 

 

예시 출력1

3

 

 

 

 

풀이

투 포인터, 슬라이딩 윈도우는 O(n^2)를 O(n)으로 풀자라는 목표를 가진다.

 

lt, anwer, sum을 0으로 초기화한다.

어떠한 특정 연속 부분의 구간을 lt~rt라고 하자.

 

sum이 m보다 작을때 까지 반복한다.

rt를 증가시키고 arr[rt]를 sum에 더한다.

sum이 m과 같은지 확인한다.

만약 sum이 m보다 크다면 sum에서 lt가 현재 가르키는 lt의 값을 빼고 lt를 증가시킨다. 그리고 이 때 비교한다.

 

rt는 증가하고 그 값을 sum에 더하고 비교, lt는 그 값을 sum에서 빼고 lt를 더하고 비교가 핵심이다.

 

rt가 끝나면 lt 빼면서 계속 확인한다.

 

 

 

 

코드

package inflearn._3_4;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

    public static int solution(int n, int m, int [] arr) {

        int answer = 0, sum = 0, lt = 0;

        for(int rt = 0; rt < n; rt++) { // rt가 증가하면서 반복
            sum += arr[rt]; // rt를 더하면 lt~rt, 즉 부분 수열의 합임
            if (sum == m) answer++; // rt 더한 후 sum이 m과 같은지 확인

            while(sum >= m) { // 크거나 같으면
                sum -= arr[lt++]; // lt가 가리키는 값을 빼고 lt 값 자체를 증가
                if (sum == m) answer++; // lt를 뺀 후 sum이 m과 같은지 확인
            }
        }


        return answer;

    }


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int [] arr = new int[N];
        st = new StringTokenizer(br.readLine(), " ");

        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        bw.write(sb.append(solution(N, M, arr)).toString());
        bw.flush();

        bw.close();
        br.close();


    }
}