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

문제

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

---

풀이(25분)

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

public class Main {

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

        st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken()); // 배열의 길이
        int k = Integer.parseInt(st.nextToken()); // 최대 뺄 수 있는 수의 개수

        int answer = 0; // 정답 추적
        int[] arr = new int[n]; // 입력받은 배열

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

        int start = 0;
        int end = 0;
        int nowK = 0;
        int count = 0;

        while(end < n){ // 끝까지 탐색 조건
            if(nowK < k){ // 아직 뺼 수 있는게 있다면
                if(arr[end] % 2 == 0){ // 짝수라면
                    count++; // 값 증가
                    end++; // 끝 인덱스 증가
                    answer = Math.max(answer, count - nowK); // 최댓값 갱신
                    continue;
                }
                end++; // 끝 인덱스 증가
                count++; // 값 증가
                nowK++; // 현재 k값 증가
                answer = Math.max(answer, count - nowK); // 최댓값 갱신
                continue;
            }
            if(nowK == k){ // 이미 최대에 다 왔다면
                if(arr[end] % 2 == 0){ // 짝수라면
                    count++; // 값 증가
                    end++; // 끝 인덱스 증가
                    answer = Math.max(answer, count - nowK); // 최댓값 갱신
                    continue;
                }
                while(arr[start] % 2 == 0){
                    count--; // 값 감소
                    start++; // 시작 인덱스 증가
                }
                count--; // 값 감소
                nowK--; // 현재 k값 감소
                start++; // 시작 인덱스 증가
                answer = Math.max(answer, count - nowK); // 최댓값 갱신
            }
        }

        System.out.println(answer);

    }
}
// start 랑 end 가 있다.
// end가 앞으로 하나씩 쭉쭉 가면서 짝수면 카운트 증가, 홀수면 카운트 감소를 한다.
// 홀수 카운트가 끝나면 최댓값이랑 비교하고 저장한다.
// 홀수 카운트가 끝났으니, start가 짝수면 카운트 감소, 홀수면 카운트 증가를 시켜준다.
// 이 때 카운트가 증가됐다면 다시 end를 증가시킨다.

 

투포인터를 활용한 문제 풀이이다. 주석에 쓰여있는 흐름은 다음과 같다.

 

1. 추가적으로 뺄 수 있는 k가 있는지 본다.

 

1-1.  더 제거할 수 있는 숫자가 있다면 end를 증가시킨다.

1-2. end를 증가시키며 값을 증가시키고, 이때 매번 answer과 count - nowK개를 비교하여 최댓값을 저장한다.(nowK를 빼주는 것은 홀수를 빼주기 위함.)

1-3. end 값을 증가시킬 때 arr[end]가 짝수라면 단순 증가를 하고, 홀수라면 nowK 또한 같이 증가해 준다.

 

2-1. nowK가 k에 도달해 더 이상 제거할 수 있는 숫자가 없다면 arr[end]를 먼저 관찰한다.

2-2. arr[end]가 짝수라면 count를 +1 하고, end 또한 +1 하며 값을 저장한다.(아직 길이를 더욱 늘릴 수 있으므로 상태를 보는 것이다.)

2-3. 홀수라면 arr[start]가 홀수가 나올 때 까지 count를 -1, start를 +1 하며 nowK가 줄어들길 기다린다.

2-4. arr[start]가 홀수가 되었다면 count를 -1, start를 +1 하고 nowK를 -1 해주어 다음 반복문에 들어갈 수 있게 해 준다.