[알고리즘] 연속부분수열

문제 설명

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

 

문제 풀이

입력받은 배열에서 합이 M이 될 수 있는 경우의 수를 구하는 문제이다.

2중 for문으로 배열을 모두 순회하며 모든 경우의 수를 확인할 수 있겠지만, N의 N제곱 만큼 연산을 실행하므로, 배열의 크기 N이 커질수록 퍼포먼스가 매우 좋지 않다.

 

2개의 포인터를 두면 N번만 연산하여 해결할 수 있다.

int lt = 0, rt

변수 lt와 rt는 각각 배열이 현재 가리키는 인덱스를 저장한다.

 

rt에 해당하는 값들을 순차적으로 더해가면서 다음과 같은 조건을 확인해야한다.

for (rt = 0; rt < n; rt++) {
    sum += arr[rt];
    if (sum == m) answer++;
    while (sum >= m) {
        sum -= arr[lt++];
        if (sum == m) answer++;
    }
}

1. rt가 가리키고 있는 배열 값을 sum에 더해준다.

2. sum과 m이 같을 경우 경우의 수를 증감한다.

3. sum이 크거나 같을 경우 배열을 지나왔던 값을 sum에서 빼준고 lt를 증감한다. 단, 지나왔던 값을 하나 빼도 현재의 sum이 m보다 클 수 있으니 while문을 사용하여 sum이 m보다 작아질 때 까지 반복하여 수행해야한다.

 

전체 소스

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        Main main = new Main();

        int n = kb.nextInt();
        int m = kb.nextInt();

        int [] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }

        System.out.println(main.solution(n, m, arr));
    }

    
    public int solution(int n, int m, int[] arr) {
        int answer = 0;
        int lt = 0, rt, sum = 0;

        for (rt = 0; rt < n; rt++) {
            sum += arr[rt];
            if (sum == m) answer++;
            while (sum >= m) {
                sum -= arr[lt++];
                if (sum == m) answer++;
            }
        }

        return answer;
    }

}