[JAVA/코딩테스트] 최대 길이 연속부분수열

설명

0과 1로 구성된 길이가 N인 수열이 주어집니다. 여러분은 이 수열에서 최대 k번을 0을 1로 변경할 수 있습니다. 여러분이 최대 k번의 변경을 통해 이 수열에서 1로만 구성된 최대 길이의 연속부분수열을 찾는 프로그램을 작성하세요.

만약 길이가 길이가 14인 다음과 같은 수열이 주어지고 k=2라면

1 1 0 0 1 1 0 1 1 0 1 1 0 1

여러분이 만들 수 있는 1이 연속된 연속부분수열은

이며 그 길이는 8입니다.

입력

첫 번째 줄에 수열의 길이인 자연수 N(5<=N<100,000)이 주어집니다.

두 번째 줄에 N길이의 0과 1로 구성된 수열이 주어집니다.

출력

첫 줄에 최대 길이를 출력하세요.

 

 

예시입력

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

 

출력

8

 

 

- 풀이 

반복문을 돌려가며 i를 오른쪽 포인트로 잡고, lt로 왼쪽 포인트를 잡아 0의 갯수를 세어가며 길이를 재고 이를 비교하였음

import java.util.*;

public class Main {

    public static void solution(int a, int b, int[] array){

        int result = 0;
        int change = 0;
        int cnt = 0;
        int lt = 0;

        for(int i=0; i<a; i++){

            if(array[i] == 0){
                change++;
            }

            while(b<change){
                lt++;
                if(array[lt] == 0){
                    change--;
                }
            }

            cnt = i-lt;

            if(result < cnt){
                result = cnt;
            }

        }

        System.out.println(result);

    }

    public static void main(String[] args) {

        Main main = new Main();
        Scanner kb = new Scanner(System.in);

        int a = kb.nextInt();
        int b = kb.nextInt();

        int[] array = new int[a];

        for(int i=0; i<a; i++){
            array[i] = kb.nextInt();
        }

        Main.solution(a, b, array);
    }

}