[JAVA] 백준 q22862 - 가장 긴 짝수 연속한 부분 수열 (large)

 

 

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

---

의식의 흐름

투 포인터를 사용해서 가장 긴 길이를 저장해두자

풀이 과정

1. 수열의 길이(N), 삭제할 수 있는 최대 횟수(K)를 입력받는다.
2. N개의 숫자를 배열(nums)에 담아둔다.
3. 삭제한 횟수(removedCnt)가 K 이하인 경우 최대 길이(maxLength)를 갱신한다.
3-1) start, end 포인터를 둔다.
3-2) removedCnt에 따라 start, end를 이동한다.

• removedCnt <= K인 경우, nums[end]의 값에 따라 removedCnt를 증가시키고 maxLength를 갱신한 후 end를 이동한다.
• removedCnt > K인 경우, nums[start]의 값에 따라 removedCnt를 감소시키고 start를 이동한다.

4. maxLength를 출력한다.

 

코드

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

public class Main {
    public static int N, K;
    public static int[] nums;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

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

        int start = 0;
        int end = 0;
        int removedCnt = 0;
        int maxLength = 0;
        while(end<N){
            if(removedCnt<=K){
                if(nums[end]%2 == 1){
                    removedCnt++;
                }
                if(removedCnt > K){
                    end++;
                    continue;
                }
                maxLength = Math.max(maxLength, end-start+1-removedCnt);
                end++;
            }
            else{
                if(nums[start]%2 == 1){
                    removedCnt--;
                }
                start++;
            }
        }

        bw.write(Integer.toString(maxLength));
        bw.flush();

        br.close();
        bw.close();
    }
}