[JAVA] 28. 최대 길이 연속부분수열 ✔

설명

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로 구성된 수열이 주어집니다.

출력

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

예시 입력 1 

14 2

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

예시 출력 1

8

 

 

---

 

내풀이 - K=2가 고정이라고 생각하고 품

 

public class MaxLength
{
    public static void main(String[] args) {

        int n= 14;
        int k = 2;
        int[] arr = {1, 1, 0,0,1,1,0,1,1,0,1,1,0,1};

        int pi=0, pj=0, answer =0, p1=-1, p2=-1;
        while (pj < n) {
            if(arr[pj] == 0){
                if(p1 == -1){
                    p1 =pj;

                }else if(p2 == -1 ){
                    p2 = pj;

                }else{
                    answer = Math.max(answer, pj-pi);

                    pi = p1+1;
                    p1 = p2;
                    p2 = pj;

                }
            }
            pj++;
        }

        System.out.println( answer+ " ");
    }
}

 

 

다른 풀이

 

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
   
     int n= in.nextInt();
        int k = in.nextInt();
        int[] arr = new int[n];
    for(int i=0;i<n;i++){
      arr[i] = in.nextInt();
    }

		// cnt는 0을 1로 바꾼 횟수
        int cnt =0, lt =0, answer =0;
        for(int rt=0; rt<n; rt++){
        
        // rt가 0을 만나면 1로 바꾸고 cnt+1
            if(arr[rt] == 0){ 
                cnt ++;
            }
            
            //cnt가 횟수를 초과하면
            while(cnt >k){
            
            	// lt를 움직이면서 1을 다시 0으로 바꿔준다
                if(arr[lt] == 0){
                    cnt --;
                }
                lt ++;
            }
            // rt가 움직일 때마다 최대 길이 값 갱신.
            answer= Math.max(answer, rt-lt+1);

        }

        System.out.println( answer+ " ");
  }
}