[Inflearn] 연속부분수열

인프런의 자바(Java)알고리즘 문제풀이 입문:코딩테스트 대비 강좌의 문제를 풀고 문제 해설을 작성해보았습니다.

 

섹션 3. Two pointers, Sliding window[효율성 : O(n^2)-->O(n)]의 4. 연속부분수열(복합적 문제) 강의편 입니다.

 

설명

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

 

출력

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

 

import java.util.Scanner;

public class 연속부분수열 {

	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<n; i++) {
			arr[i] = sc.nextInt();
		}
		
		System.out.println(solution(n, m, arr));
	}
	
	public static int solution(int n, int m, int[] arr) {
		int cnt=0;
		
		for(int i=0; i<n; i++) {
			int sum=0;
			for(int j=i; j<n; j++) {
				sum += arr[j];
				if(sum > m) {
					break;
				}else if(sum == m) {
					cnt++;
				}
			}
		}
		return cnt;
	}

}

>>해설

n : 수열의 크기

m : 연속 부분 수열에서 특정 합의 값

arr : 수열 크기의 배열

-> arr 배열에서 연속된 원소들의 합이 m이 되는 경우를 구해야 한다.

 

이중 반복문으로 진행하는데

 

i를 0부터 n까지 반복하고 원소의 합계를 누적시킬 sum 변수를 0으로 초기화한다.

j를 i부터 n까지 반복하고 sum에 원소의 값을 저장하고 sum과 m을 비교한다.

 

[비교 1] - sum이 m보다 크면 반복문을 빠져나옴.

[비교 2] - sum이 m과 같으면 cnt 값을 증가시킨다.

 

 

cnt 값을  리턴하고 프로그래밍을 종료한다.