[코딩테스트] 연속 부분수열

 

문제

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을 넘지 않는 자연수이다.

 

출력

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

 

 

 

예시 입력

8 6
1 2 1 3 1 1 1 2

예시 출력

3

 

 

 

 

 

문제 풀이

 

[첫번째 풀이]

import java.util.*;

public class Main {
    public int solution(int n, int m, int[] numbers) {
        int sum = 0, count = 0, start = 0;

        for (int i=0; i<n; i++) {
            sum += numbers[i];

            while (sum > m) {
                sum -= numbers[start];
                start++;
            }
            if (sum == m) count++;
        }

        return count;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] numbers = new int[n];
        for (int i=0; i<n; i++) {
            numbers[i] = scanner.nextInt();
        }

        Main main = new Main();
        System.out.println(main.solution(n, m, numbers));
    }
}

(Time 803ms / Memory 33MB)

 

 

 

- 더한 값, 합이 제시된 m의 값과 같은 값의 수, 더해질 시작점을 변수로 잡고 for 문 한번만에 해결할 수 있도록 코딩해봤다.