[Gold V] 가장 긴 짝수 연속한 부분 수열 (large) - 22862

문제 링크

성능 요약

메모리: 92168 KB, 시간: 448 ms

분류

두 포인터

제출 일자

2025년 2월 3일 05:02:12

문제 설명

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

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

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

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

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

입력

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

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

출력

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

제한

$1 \le N \le 1,000,000$ 

$1 \le K \le 100,000$ 

$1 \le$ 원소의 값 $\le 10^6$ 

문제 풀이

코드

package BOJ_22862_가장긴짝수연속한부분수열large;

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static int N, K, oddCnt;
    static boolean[] isOdd;
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
//        br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_22862_가장긴짝수연속한부분수열large/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

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

        if(N == 1){
            bw.write(isOdd[0] ? "0" : "1");
        }
        else{
            if(oddCnt <= K) {
                bw.write(String.valueOf(N-oddCnt));
            }
            else{
                int left=0, right=0;
                int cnt = K;
                int evenCnt = 0;
                int maxLen = 0;

                while(right < N && left <= right){
                    if(!isOdd[right]){ // 오른쪽 짝수일때
                        evenCnt++;
                        right++;
                    }
                    else{ // 오른쪽 홀수일때
                        if(cnt > 0) { // 홀수 더 지울 수 있을때
                            cnt--;
                            right++;
                        }
                        else{ // 홀수 지울 수 없을때는 왼쪽줄여야됨
                            if(!isOdd[left]) { // 왼쪽짝수없애기
                                evenCnt--;
                                left++;
                            }
                            else{ // 왼쪽홀수없애기
                                cnt++;
                                left++;
                            }
                        }
                    }
                    maxLen = Math.max(maxLen, evenCnt);
                }
                sb.append(maxLen).append("\n");
            }
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}