자바(백준) 22862 가장 긴 짝수 연속한 부분 수열

오답 노트 & 새로 알게 된 점

문제에서 홀수를 K개 없애면서 짝수로 이루어진 연속된 수열 중 가장 긴 길이를 구하는 것이다.

 

만약에 K개의 홀수를 골라 길이를 구한다고 생각하면 바로 TLE가 난다.

 

그래서 투 포인터를 사용하여 앞에서부터 홀수이면 cnt를 증가시키면서

cnt가 K개 이하일 때까지 e를 늘리면서 길이의 max값을 구하면 된다.

 

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N, K;
    static int A[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = atoi(st.nextToken());
        K = atoi(st.nextToken());
 
        A = new int[N + 1];
 
        st = new StringTokenizer(br.readLine());
 
        for (int i = 1; i <= N; i++) {
            A[i] = atoi(st.nextToken());
        }
 
        pro();
    }
 
    static void pro() {
        int e = 0, len = 0, cnt = 0;
 
        for (int s = 1; s <= N; s++) {
            if(cnt >= 1 && A[s-1] % 2 != 0) cnt--;
 
            while (e + 1 <= N && cnt <= K) {
                if(A[++e] % 2 != 0) cnt++;
            }
 
            len = Math.max(len, e - s + 1 - cnt);
        }
 
        System.out.println(len);
    }
}