java - 최대 길이 연속부분수열 (투포인트)

import java.util.Scanner;

public class MaximumLengthContinuousSubsequence {
    public static int solution(int n, int k, int[] bins) {
        int answer = 0, lt = 0, convertCnt = 0;
        for (int rt = 0; rt < n; rt++) {
            if (bins[rt] == 0) convertCnt++;
            while (convertCnt > k) {
                if (bins[lt] == 0) convertCnt--;
                lt++;
            }
            answer = Math.max(answer, rt - lt + 1);
        }
        return answer;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int[] bins = new int[n];

        for (int i=0; i<n; i++) {
            bins[i] = in.nextInt();
        }
        System.out.println(solution(n, k, bins));
    }
}

 

 

문제 해설

---

이 문제도 마찬가지로 2포인터를 사용하여 O(n)의 시간복잡도 로 해결하는 문제이다.
Left point 와 right point를 사용하여 right point 가 1씩 증가하는데 0 을 만나면 counting 한다.
Counting 한 값이 k 보다 클 경우 left point 의 현재위치의 값이 0인지 확인하고

0일 경우 counting 값을 1 빼고 left point 를 1 증가 시킨다.

그리고 answer 와 포인트 와 포인트 간의 간격 중 더 큰값을 answer에 저장하고 마무리한다.