가장 긴 짝수 연속한 부분 수열

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

풀이 생각
1. K번 삭제한 수열이 짝수로 이루어져있다.
2. 가장 길다면 모든 수열의 수를 카운트하다 홀수 일때 count를 줄이면 되겠다.

소스 코드

main

public static void main(String[] args) throws IOException {

 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        k = Integer.parseInt(s[1]);
        check = new boolean[n+1];

        arr= new int[n+1];
        String[] s1 = br.readLine().split(" ");
        for(int i=1; i<=n; i++){
            int num = Integer.parseInt(s1[i-1]);
            arr[i]=num;

            if(num%2!=1){
            //짝수일때
                check[i]=true;
            }
        }
        solve();
        System.out.println(max);
    }

    public static void solve(){

        while(end <= n){

            if(count <k){
                // count < k 를 만족할 때까지 계속해서 count를 증가하며 수열의 길이를 증가시킬 수 있다.
                if(!check[end]){
                 
                    count++;
                }
                end++;
                max = Math.max(max,end-start-count);
            }else if(check[end]){
                //짝수겠지
                end++;
                max = Math.max(max,end-start-count);
            }else if(count==k && !check[end]){
                // 카운트는 맞는데 , 홀수일때
                if(!check[start]){ // first가 있던 위치의 수가 홀수일 때 count를 낮추며 아닌 경우에는 count는 냅둡니다.
                    count--;
                    //홀수면 카운트 감소
                }
                start++;
            }


        }
      }
  }

슬라이딩 윈도우

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        arr = new int[n];
        check = new boolean[n + 1];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int p = 0; //짝
        int q = 0; //홀
        int answer = 0;

        int e = 0;

        //슬라이딩 윈도우 -> 윈도우 크기만큼 end 길이을 늘려주면서 연산을 한다
        for (int i = 0; i < n; i++) {
            if (arr[i] % 2 == 0) {
                p++;
            } else {
                q++;
            }
            if (q == k) { // 홀수가 k개가 될때까지 홀수 짝수의 개수와 e의 위치를 옮겨준다 //빼줄거니깐
                e = i;
                break;
            }
        }
        answer = p;

        for (int i = 0; i < n; i++) { // i는 start pointer
            while (q <= k) {  // 삭제한 홀수의 개수가 k개 이하일 때 까지
                if (q == k) {
                    answer = Math.max(answer, p);
                } //삭제한 홀수개수가 k개일때
                e++;

                if (e >= n) {
                    e--;
                    break;
                } //배열의 끝부분을 넘어서게 되면 while문을 빠져나간다

                if (arr[e] % 2 == 0) { //짝수일 경우
                    p++;
                } else { //홀수일 경우
                    q++;
                }

            }
            if (arr[i] % 2 == 0) {
                p--; // 다음 시작점으로 옮기기 전에 현재 시작점에 있는 수가 				홀수인지 짝수인지 판별하고 빼준다
            } else {
                q--;
            }
        }
        System.out.println(answer);
    }
}

공부 할 것

슬라이딩 윈도우 , 그리디

참고

https://spacefordeveloper.tistory.com/416