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

📌 문제 설명

0과 1로 구성된 길이가 N인 수열이 주어집니다. 이 수열에서 최대 K번 0을 1로 변경하여 만들 수 있는 1로만 이루어진 연속 부분수열의 최대 길이를 구하는 프로그램을 작성하세요. 예를 들어 N=14이고, 수열과 K가 다음과 같다면

1 1 0 0 1 1 0 1 1 0 1 1 0 1
K = 2

 

최대 2번 0을 1로 바꿨을 때 만들 수 있는 가장 긴 1의 연속부분수열은 아래와 같습니다.

[1 1 0 0 1 1 0 1 1 0 1 1 0 1]
           ↑-----------↑
           연속된 길이 = 8

---

📝 입력 & 출력

입력

• 첫 줄: 수열의 길이 N과 정수 K (5 ≤ N < 100,000)
• 둘째 줄: 0과 1로 구성된 N개의 정수

출력

• 첫 줄에 최대 길이 출력

---

🔸 예제 입력 & 출력

예제 입력 1

14 2
1 1 0 0 1 1 0 1 1 0 1 1 0 1

 

예제 출력 1

8

---

💡 해결 방법

• 이 문제는 투 포인터 (슬라이딩 윈도우) 기법을 사용하여 해결할 수 있습니다.
• 윈도우 안에 있는 0의 개수를 세면서 그 개수가 K를 초과하면 왼쪽 포인터를 가장 먼저 등장한 0 다음 인덱스로 이동시킵니다.
• 각 구간마다 rt - lt + 1을 계산하여 최대 길이를 갱신합니다.

---

💻 코드 구현 (Java)

package partTwoPointers;

import java.util.*;

public class Problem6 {
	public int solution(int n, int k, int[] arr){
		int lt = 0, cnt = 0, result = 0;
		for(int rt = 0; rt < n; rt++) {
			if(arr[rt] == 0) cnt++;
			if(cnt > k) {
				while(arr[lt] != 0) lt++;
				lt++;
				cnt--;
			}
			result = Math.max(result, rt - lt + 1);
		}
		return result;
	}
	
	public static void main(String[] args) {
		Problem6 T = new Problem6();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int k = kb.nextInt();
		int[] arr = new int[n];
		for(int i = 0; i < n; i++) {
			arr[i] = kb.nextInt();
		}
		System.out.print(T.solution(n, k, arr));
		kb.close();
	}
}

---

📖 코드 설명

1️⃣ 슬라이딩 윈도우 탐색

for(int rt = 0; rt < n; rt++) {
	if(arr[rt] == 0) cnt++;

• 우측 포인터(rt)를 이동시키며 0을 만났을 때 cnt 증가

2️⃣ 0의 개수가 K 초과 시 왼쪽 포인터 이동

if(cnt > k) {
	while(arr[lt] != 0) lt++;
	lt++; // 가장 먼저 등장한 0 다음 인덱스로 이동
	cnt--;
}

• lt를 가장 먼저 등장한 0을 지나쳐 다음 인덱스로 이동시킴

3️⃣ 최대 길이 계산

result = Math.max(result, rt - lt + 1);

• 윈도우 크기 중 최대값을 저장

---

⏳ 시간 복잡도 분석

• 각 포인터가 배열을 한 번씩만 이동 → O(N)

---

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

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