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

백준 22862번 문제 - 가장 긴 짝수 연속한 부분 수열 

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

---

문제 분석

 

 

• 수열에서 최대 K번 숫자를 삭제해 가장 긴 짝수 연속한 부분 수열 길이를 출력해라

---

해결 키 포인트

 

• 투포인트로 문제 풀이
• 최대 K번 삭제 (무조건 K번을 삭제할 필요 없다)
• 은근 까다로웠던 부분 : K가 0이어도 뒤에 홀수가 나오기 전에는 end가 증가해도 된다.
  • 나는 처음 알고리즘을 짤 때 K가 0번이 되기 전까지 end를 증가 시켰다.
    → 하지만 K가 0번일때까지 end를 증가해도 됨

 

투 포인터 문제 연속한 부분 수열 문제 보편적 풀이

 

• start, end 포인터 0에서 시작
• end가 조건에 어긋나기 전까지 증가 : while문 이용
• result는 현재 result 값과 방금 구해진 result 값 중에 큰 값으로 설정
• start 증가 

---

코드

 

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

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

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

        int[] nums = new int[N];

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

        int result = 0;
        int start = 0, end = 0;
        int newK = K;

        while (end < N) {
            while (end < N && newK >= 0) {
                if (nums[end] == 1) {
                    newK--;
                }
                end++;
            }
            result = Math.max(result, end - start - (K - newK));
            if (nums[start] == 1) {
                newK++;
            }
            start++;
        }

        System.out.println(result);
    }
}