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

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

https://www.acmicpc.net/problem/22862

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

---

2. 내가 푼 방법

start 변수와 end 변수를 이용한 투포인터 알고리즘을 이용했다.

 

핵심 코드는 아래와 같다.

int result = 0;
int deleteChance = 0;
int start = 0;
int end = 0;

while (end < N) {
    if (arr[end] % 2 == 0) {
        result = Math.max(result, end - start + 1 - deleteChance);
    }
    else {
        deleteChance++;

        while (deleteChance > K) {
            if (arr[start++] % 2 == 1) deleteChance--;
        }
    }

    end++;
}

end 인덱스가 홀수를 가지면 홀수를 삭제할 수 있는 기회를 카운팅함과 동시에, K번 이상일 경우 start 인덱스를 홀수를 가지는 값까지 증가시키는 과정을 가진다. end 인덱스가 짝수를 가지면 현재 범위 길이를 계산한다.

---

3. 자바 코드

깃허브 풀이 주소

https://github.com/geujeog/BOJ/blob/main/B22862.java

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

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[] arr = new int[N];
        
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        int result = 0;
        int deleteChance = 0;
        int start = 0;
        int end = 0;
        
        while (end < N) {
            if (arr[end] % 2 == 0) {
                result = Math.max(result, end - start + 1 - deleteChance);
            }
            else {
                deleteChance++;
                
                while (deleteChance > K) {
                    if (arr[start++] % 2 == 1) deleteChance--;
                }
            }
            
            end++;
        }
        
        bw.write(result+"");
        
        br.close();
        bw.flush();
        bw.close();
    }
}

---

4. 결과 및 회고

생각한 코드가 맞긴 했는데 뭔가 긴가민가하면서 풀었던 것 같다. 처음에 감을 못 잡아서 그랬나?

더 많이 풀어보자아!