Two Pointer_최대 길이 연속부분수열

✅ 0과 1로 이루어진 수열이 있다. 이 수열에서 최대 k번 0을 1로 바꿀 기회가 주어졌을 때, 1로만 이루어진 연속 부분 수열의 최대 길이는??

class Main {

    public int solution(int n, int k, int[] intArr){
    int answer= 0;
    int lt=0;
    int count=0; //0을 1로 바꾼 횟수
        for(int rt=0; rt<n; rt++){
            if(intArr[rt] == 0) count++;
            if(count>k){
                if(intArr[lt] == 0) count--;
                lt++;
            }
            answer= Math.max(answer, rt-lt+1);
        }

    return answer;
}
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        int k= sc.nextInt();
        int[] intArr= new int[n];
        for(int i=0; i<n; i++){
            intArr[i] = sc.nextInt();
        }
        System.out.print(T.solution(n, k, intArr));
    }
}

//⭐️input:
// 14 2
// 1 1 0 0 1 1 0 1 1 0 1 1 0 1
//⭐️output:
//8

🔵 ThingsILearned

✔️ How to solve

1. rt가 앞서가고, lt가 따라온다.
   
2. rt가 가다가 0을 만나면 1로 바꾸고, count를 1 증가시킨다.
   
3. 그리고 1로 연속된 부분 수열의 길이를 구한다. rt-lt+1
   
4. 그러다가 count가 최대 횟수 k를 넘어서면, lt가 0인 곳을 찾아 lt를 거기로 설정하고 count에서 1을 뺴서 최대 횟수를 넘어서지 않도록 한다.
   

🟢 내가 푼 방법

class Main {

    public int solution(int n, int k, int[] intArr){
    int answer= 0;
    int lt=0;
    int rt=lt;
    int count=0; //0을 1로 바꾼 횟수
    int length= 0;
    while(lt<n && rt<n){
        if(count<=k) {
            if (intArr[rt] == 0) {
                length = rt - lt - 1;
                rt++;
                count++;
            } else {
                length = rt - lt + 1;
                rt++;
            }
        }else {
            lt++;
            rt=lt;
            count=0;
            length=0;
    }
        if(length>answer) answer=length;
    }

    return answer;
}
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        int k= sc.nextInt();
        int[] intArr= new int[n];
        for(int i=0; i<n; i++){
            intArr[i] = sc.nextInt();
        }
        System.out.print(T.solution(n, k, intArr));
    }
}