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

💡문제

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

문제 링크

성능 요약

메모리: 120328 KB, 시간: 456 ms

---

🤔접근법

범위 체크 및 시간복잡도 예상

• 1 ≤ N ≤ 1,000,000
• 1 ≤ K ≤ 100,000
• 1 ≤ 원소의 값 ≤ 1,000,000
• $O(N)$이하 가능하다.

풀이법

❌ 접근 방법. 완탐

1. 원소를 1 ~ K번까지 삭제→ $O(K)$
2. 어떤 원소를 삭제할지 선택 → $O(N)$

➡️ 해당 풀이법의 시간 복잡도 : $O(NK)$
시간초과

⭕ 접근 방법. 투포인터, 슬라이딩 윈도우

1. 수열에서 연속한 부분수열의 구간을 보는데 start = 0, end = 0으로 두고 시작
2. 구간을 늘려가면서 구간 내에 존재하는 홀수의 개수가 K보다 작은지 확인
   1. 만약 범위내에 홀수의 개수가 K보다 작거나 end를 증가시켜 구간을 늘린다.
   2. 크다면 “K번만에 삭제해서 짝수로 이루어진 연속된 부분 수열”을 만들 수 있으므로 가장 긴 길이 갱신
   3. 새로운 구간을 보기 위해서 start를 증가 후 반복→ $O(N)$
      스타트를 증가시켰으니 구간에서 제외된 홀수의 개수만큼 구간 내 홀수의 개수를 정정해주어야한다.

➡️ 해당 풀이법의 시간 복잡도 : $O(N)$

---

🤯FAIL

답을 봐서 문제를 푼 경우

• 해결이 되지 않은 부분 : 최대 K번까지 수를 지울 수 있다고 했을때 K번을 다 삭제하는게 최대 길이를 보장한다는 것을 생각하지 못했다.
• 정답의 로직은 ?
  구간을 보되 홀수의 개수만 저장해두고 구간의 길이 - 홀수의 개수를 하면 짝수로만 이루어진 부분 수열의 길이라는 것을 이용하였다.

---

👩‍💻 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_22862 {
    static int N; // 배열의 요소 개수
    static int K; // 허용된 홀수의 최대 개수
    static int arr[]; // 입력 정수를 저장하는 배열
    static int max = Integer.MIN_VALUE; // 최대 부분 배열 길이를 저장하는 변수

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // N과 K를 입력으로 받음
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        // 배열 요소를 입력으로 받음
        st = new StringTokenizer(br.readLine());
        arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int start = 0; // 현재 부분 배열의 시작 인덱스
        int end = 0;   // 현재 부분 배열의 끝 인덱스
        int odd = 0;   // 현재 부분 배열에 포함된 홀수의 개수

        // 최대 부분 배열 길이를 찾기 위한 슬라이딩 윈도우 알고리즘
        while (start < N) {
            while (end < N && odd <= K) {
                if (arr[end] % 2 != 0) {
                    odd++; // 홀수를 만나면 홀수 개수 증가
                }
                end++;
            }

            // 최대 부분 배열 길이 업데이트
            max = Math.max(max, end - start - odd);

            // 윈도우를 이동하여 시작 인덱스 증가
            if (arr[start] % 2 != 0) {
                odd--; // 현재 부분 배열에서 홀수를 제거하므로 홀수 개수 감소
            }
            start++;
        }

        // 최대 부분 배열 길이 출력
        System.out.println(max);
    }
}