섹션 3 투 포인터 & 슬라이딩 윈도우 - 4. 연속 부분수열

📌 문제 설명

N개의 수로 이루어진 수열이 주어질 때, 이 수열에서 연속 부분수열의 합이 특정 숫자 M이 되는 경우의 수를 구하는 프로그램을 작성하세요. 예를 들어 N=8, M=6이고 수열이 다음과 같다면 

1 2 1 3 1 1 1 2

 

합이 6이 되는 연속 부분수열은 다음과 같이 3가지입니다.

• {2, 1, 3}
• {1, 3, 1, 1}
• {3, 1, 1, 1}

---

📝 입력 & 출력

입력

• 첫째 줄: 정수 N(1 ≤ N ≤ 100,000), M(1 ≤ M ≤ 100,000,000)
• 둘째 줄: 수열의 N개 원소 (각 원소는 1,000 이하 자연수)

출력

• 첫 줄에 합이 M이 되는 연속 부분수열의 개수 출력

---

🔸 예제 입력 & 출력

예제 입력 1

8 6
1 2 1 3 1 1 1 2

 

예제 출력 1

3

---

💡 해결 방법

• 이 문제는 슬라이딩 윈도우 또는 투 포인터 기법으로 해결할 수 있습니다.
• 왼쪽 포인터(lt)와 오른쪽 포인터(rt)를 이동시키며 현재 윈도우의 합을 관리합니다.
• 합이 M보다 작으면 오른쪽 포인터를 이동시키고, 크거나 같으면 왼쪽 포인터를 이동시킵니다.

---

💻 코드 구현 (Java)

package partTwoPointers;

import java.util.*;

public class Problem4 {
	public int solution(int n, int m, int[] arr){
		int result = 0, sum = 0;
		int lt = 0;
		
		for(int rt = 0; rt < n; rt++) {
			sum += arr[rt];
			if(sum == m) result++;
			
			while(sum >= m) {
				sum -= arr[lt++];
				if(sum == m) result++;
			}
		}
		
		return result;
	}
	
	public static void main(String[] args) {
		Problem4 T = new Problem4();
		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));
		kb.close();
	}
}

---

📖 코드 설명

1️⃣ 슬라이딩 윈도우 시작

sum += arr[rt];
if(sum == m) result++;

• 오른쪽 포인터(rt)를 증가시키며 누적합 계산

2️⃣ 합이 M 이상인 경우 왼쪽 포인터 이동

while(sum >= m) {
	sum -= arr[lt++];
	if(sum == m) result++;
}

• 합이 M보다 크거나 같을 때 왼쪽 포인터를 이동시켜 윈도우 축소
• 줄였을 때 합이 M이 되면 카운트 증가

---

⏳ 시간 복잡도 분석

• 각 포인터는 배열을 한 번씩만 이동하므로 O(N)의 시간 복잡도

---

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

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