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

문제 링크: https://www.acmicpc.net/problem/22862

22862번: 가장 긴 짝수 연속한 부분 수열 (large)

 

▶문제

길이가 N인 수열 S가 있다. 수열 S는 1 이상인 정수로 이루어져 있다.

수열 S에서 원하는 위치에 있는 수를 골라 최대 K번 삭제를 할 수 있다.

예를 들어, 수열 S가 다음과 같이 구성되어 있다고 가정하자.

수열 S : 1 2 3 4 5 6 7 8

수열 S에서 4번째에 있는 4를 지운다고 하면 아래와 같다.

수열 S : 1 2 3 5 6 7 8 

수열 S에서 최대 K번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구해보자.

---

▶입력

수열 S의 길이 N와 삭제할 수 있는 최대 횟수인 K가 공백으로 구분되어 주어진다.

두 번째 줄에는 수열 S를 구성하고 있는 N개의 수가 공백으로 구분되어 주어진다.

---

▶출력

수열 S에서 최대 K번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다.

---

▶해설

투 포인터로 접근했습니다. count라는 변수를 이용하여 부분 수열 사이에 홀수의 수를 저장하고, second-first-count를 이용하여 수열의 길이를 구했습니다. 고려해야 할 사항이 한 가지 있습니다. 

count==K이지만 second의 숫자가 짝수라 count가 증가하지 않아 더 긴 수열을 찾을 수 있다. 이 조건만 적용 하신다면 쉽게 구하실 수 있습니다.  

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
 
 
public class Main {
    static int n, k;
    static int [] arr;
    static int max;
    static int count;
    static boolean [] check;
    static int first=1, second=1;
    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 (second<=n){
            if(count<k){ // count<k 를 만족할 때까지 계속해서 count를 증가하며 수열의 길이를 증가시킬 수 있다. 
                if(!check[second]){
                    count++;
                }
                second++;
                max = Math.max(max,second-first-count);
            }
            else if(check[second]){ // count==K를 만족하지만 뒤 숫자가 짝수여서 더 길게 가능하다.
                second++;
                max = Math.max(max,second-first-count);
            }
            else if(count==k && !check[second]){ // count==K가 됐으며 뒤의 수도 홀수일 때 first를 증가시킵니다. 
                if(!check[first]){ // first가 있던 위치의 수가 홀수일 때 count를 낮추며 아닌 경우에는 count는 냅둡니다.
                    count--;
                }
                first++;
            }
        }
    }
}