#9 자바(JAVA) 알고리즘 문제풀이 : 코딩테스트 대비 / 연속 부분 수열

N개의 수로 이루어진 수열이 주어짐
이 수열에서 연속 부분 수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하시오
- 첫째 줄에 N ( 1<= N <= 100,000 ),M ( 1<= N <= 100,000 ) 이 주어진다.
- 수열의 원소값은 1,000을 넘지 않는 자연수임
- 첫째 줄에 경우의 수를 출력한다.

 

< 입력 >

8 6
1 2 1 3 1 1 1 2

 

< 출력 >

 

3

첫 줄에 N , 둘째 줄에 M을 입력한다. 

---

import java.util.Scanner;

public class Inflearn28 {
    public int Solution(int N ,int M, int[] A) {
        int sum = 0;        // 연속 수열의 합을 저장할 변수
        int answer =0 ;      //  출력을 위한 변수
        int lt = 0;
        for(int rt = 0; rt<N; rt++) {
            sum += A[rt];
            if(sum == M) {
                answer ++;
            }
            while(sum>=M) {
                sum -= A[lt++];
                if(sum == M) {
                    answer ++;
                }
            }
        }
        return answer;
    }
    public static void main(String[] args) {
        Inflearn28 inflearn28 = new Inflearn28();
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int M = scanner.nextInt();
        int[]A = new int[N];
        for(int i=0; i<N; i++)  {
            A[i] = scanner.nextInt();
        }
        System.out.println(inflearn28.Solution(N,M,A));
    }
}

 

N 개의 숫자를 배열에 넣어주고,

배열의 왼쪽부터 차례대로 탐색을 할 변수 LT ,RT 를 만들어준다 .

 

RT 는 증가하면서 원하는 합이 되면 answer 을 증가시켜주고 ,

sum이 M(원하는 합) 보다 크거나 같아진다면

배열에서 lT의 값을 빼주고 인덱스를 증가시켜주어 다시 sum이 M과 같은지 검사한다.

 

 

 

 

 

 

 

출처 : https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84/dashboard 

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 - 인프런 | 강의