[Algorithm] 연속 부분수열

문제

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가지입니다.

 

또 이중 for문을 돌면서 풀이하면 쉽겠지만 그렇게 되었을 경우 시간복잡도가 O(N^2)가 되기 때문에 만약 N이 0~100000000 M도 0~1000000정도 되는 경우에는 엄청난 크기가 되어버린다. 

 

그래서 저번에 배웠던

슬라이딩 윈도우(https://suucong.tistory.com/74)알고리즘과 투포인터(https://suucong.tistory.com/73)알고리즘을 합쳐서 시간복잡도가 O(N)이 되도록 구현해보았다. 

포인터를 i와 j로 두고, 계속 i를 증가시키면서 더해주고, window가 M보다 클 경우에 j를 M보다 크지 않을 때까지 반복해서 뺀다.

뺀 값이 M과 일치할 경우 answer에 1을 더해주는 알고리즘이다. 이 경우에 시간복잡도가 O(N)이 된다!

코드로 구현해본 것을 작성해보겠다.

import java.util.Scanner;

public class Section3_4_MyVer {
    private int solution(int n, int m, int[] list) {
        int answer = 0;
        int window = list[0];
        int j = 0;

        for(int i = 1; i < n; i++) {
            window += list[i];
            while(window > m && j >= 0) {
                window -= list[j++];
            }
            if(window == m) answer++;
        }

        return answer;
    }

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

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

이와 같이 코드를 구현할 수 있었다.