연속 부분수열

설명

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

 

소스 코드1

import java.util.Scanner;

public class Main {
    public static int solution(int N, int M, int[] arr) {
        int ans = 0;
        for (int i = 0; i < N; i++) { //arr 도는 루프
            int sum = 0;
            int j = 0;
            while (sum < M && (i + j) < arr.length) { //sum이 M을 넘지 않을 때까지 인덱스 i부터 차례로 계속 더한다. 
                sum += arr[i + j];
                j++;
                if (sum == M) { //값을 찾으면 ans 카운트, 만약 sum 넘었으면 그냥 while문 종료
                    ans++;
                }
            }

        }
        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextInt();
        }

        System.out.println(solution(N, M, arr));
    }
}

 

 

소스코드 2

import java.util.Scanner;
//연속 부분수열 다른 풀이

public class Main {
    public static int solution(int N, int M, int[] arr) {
        int ans = 0;
        int lt = 0, rt = 0;
        int sum = 0;
        while (rt < N) {
            if (sum == M) { //값을 찾았을 때 ans카운트 후 lt 한칸 올리며 lt값을 빼준다
                ans++;
                sum -= arr[lt++];
            } else if (sum > M) {  //M 초과했을 경우 -> lt 한칸 올려주며 그 전 lt값 빼주기
                sum -= arr[lt++];
            } else { //M보다 작을 때 -> 현재 arr[rt]값을 더한 후 rt카운트
                sum += arr[rt++];
                if (sum == M && rt == N) { //rt가 마지막 인덱스에 도착했을 때 sum과 M이 같다면
                                           //while문이 바로 끝나므로 ans 카운트 해주고 종료
                    ans++;
                }
            }

        }

        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextInt();
        }

        System.out.println(solution(N, M, arr));
    }
}