[Java] 백준 22682번 : 가장 긴 짝수 연속한 부분 수열 (large)

문제

https://www.acmicpc.net/problem/22862

 

접근 방법

1. 수열 에서 최대 K번 숫자를 지워서 제일 긴 짝수 수열을 만드는 문제이다.
2. 부르트포스로 셀 수 있지만 시간초과가 발생한다고 생각했다.
3. 따라서 투 포인터로 문제를 푸는 방식을 생각했다.
4. 포인터 S를 0 포인터 E를 0으로 두고 E를 경계선이라 생각하며 최대값을 교환해 주었다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static StringBuilder sb;
    private static BufferedReader br;
    private static StringTokenizer st;
    private static int N,K;
    private static int[] arr;
    private static int count = 0;
    private static int max = Integer.MIN_VALUE;

    //입력
    public static void input() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        arr = new int[N];
        st= new StringTokenizer(br.readLine());
        for(int i = 0 ; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken())%2;
        }
    }

    //실행
    public static void process() {
        int s = 0;
        int e = 0;

        while(e<N){
            if(count<K){
                if(arr[e]==0){
                    e++;
                    max = Math.max(max,e-s-count);

                }else{
                    count++;
                    e++;
                    max = Math.max(max,e-s-count);
                }
            }else{
                if(arr[e]==0){
                    e++;
                    max = Math.max(max,e-s-count);
                }else{
                    //이 부분이 중요하다. count 값이 K만큼 존재하는데 arr[e] == 1일때
                    //arr[s] == 0 이면 그냥 s++;
                    //arr[s] == 1 이면 count --; s++;
                    if(arr[s]==1){
                        count--;
                    }
                    s++;
                }

            }
        }
        System.out.println(max);

    }


    public static void main(String[] args) throws Exception {
        input();
        process();
    }
}