자바 알고리즘 문제 풀이 Two pointers, Sliding window Q04_ 연속 부분수열

설명

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

출력

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

 

예시 입력1	예시 출력
8 6 1 2 1 3 1 1 1 2	3

 

코드

내가 입력한 코드

package twoPointers_SlidingWindow;

import java.util.Scanner;

public class Q04 {
	
	public int solution(int N, int M, int[] arr) {
		int answer = 0;
		int sum = 0;
		
		
		for(int i = 0;i < N;i++) {
			sum = arr[i];
			
			for (int j = i+1; j < N; j++) {
				sum += arr[j];
				
				if(sum == M) {
					answer++;
					break;
				}else if(sum > M) {
					break;
				}
			}
			
		}
		
		return answer;
	}
	
	public static void main(String[] args) {
		Q04 T = new Q04();
		Scanner kb = new Scanner(System.in);
		int N = kb.nextInt();
		int M = kb.nextInt();
		int[] arr = new int[N];
		
		for(int i = 0;i < M;i++) {
			arr[i] = kb.nextInt();
		}
		
		System.out.println(T.solution(N,M,arr));
		
	}
}

---

해설 코드

import java.util.*;
class Main {	
	public int solution(int n, int m, int[] arr){
		int answer=0, sum=0, lt=0;
		for(int rt=0; rt<n; rt++){
			sum+=arr[rt];
			if(sum==m) answer++;
			while(sum>=m){
				sum-=arr[lt++];
				if(sum==m) answer++; 
			}
		}
		return answer;
	}

	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		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.print(T.solution(n, m, arr));
	}
}

 

 

풀이 및 정리 

예를 들어 수열이 1 2 1 3 1 1 1 2와 같고 합이 6인 횟수를 세어보자!
- 먼저 6과 비교할 합계 변수 sum을 선언
- 자리수 이동을 위한 lt, rt 변수 선언!

lt rt
1	2	1	3	1	1	1	2

먼저 sum 변수에 배열의[rt] 값을 더해준다. 그리고 sum이 6보다 크거나 같은지 비교합니다. sum이 6보다 작다면 계속 arr[rt]값을 sum에 더해줍니다. sum 크다면 arr[lt++]값을 sum에서 빼줍니다. arr[lt++] 값을 빼주게되면 sum변수에 처음 더해준 값을 제거 해주면서 처음 값이 제거 된다고 볼 수 있다.