[PS] 인프런 강의 - Two Pointers, Sliding window, Math 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을 넘지 않는 자연수이다.

 

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

 

▣ 입력예제 1
8 6
1 2 1 3 1 1 1 2

 

▣ 출력예제 1
3

 

풀이

two pointer, lt와 rt를 두고 왼쪽 인덱스에서 오른쪽 덱스까지의 합이 m과 같은지 계속 체크해가면서 인덱스를 이동하는 sliding window 문제이다.

 

 

처음에 풀 때 아이디어는 맞았는데, 세부 조건들이 헷갈려서 계속 틀렸다. 특히 while문으로 lt를 계속 이동시킬 수도 있다는 거랑, sum 값이 조건에 따라 계속 변동하면서 다시 체크해야 한다는 게 조금 어려웠다.

 

• sum == m이면 answer++;(답 카운트)  
• sum >= m 이 아닐때까지 while문 돌림. sum -= 맨 왼쪽값; (lt 우측한칸 이동)
  • sum값이 바뀌었으므로 다시 체크, sum==m이면 answer++;(답 카운트)

 

* while문을 쓰는 이유는,  예를 들어 1 (lt) , 1, 1, 1 ,1, 5(rt) 일 경우 lt부터 rt까지의 합이 m과 같거나 클때까지 lt를 계속 이동시켜야 하기 때문이다.

 

자세한 풀이는 주석으로 달아놓았다.

 

코드

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		int n = in.nextInt();//배열 개수
		int m = in.nextInt();//합이 m이 되는 연속부분수열 몇가지인지 구하기
		int[] arr = new int[n];
		
		for(int i=0; i<n; i++) {
			arr[i] = in.nextInt();
		}
		
		int answer = 0, sum = 0;
		int lt = 0;
		for(int rt=0; rt<n; rt++){ //(1) rt 증가
			sum += arr[rt]; // (2) rt 인덱스 값 누적합
			
			if(sum == m) answer++; //(3) sum이 m과 같으면 카운트
			//주의!!!
			while(sum >= m) { //(4) (3)을 거친 sum이 m보다 크거나 같으면
				sum-= arr[lt++]; //맨 왼쪽 값 빼고
				if(sum == m) answer++; //m과 같으면 카운트
			}
		}
		
		System.out.print(answer);
	}
}