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

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

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

문제

길이가 N인 수열 S가 있다. 수열 S는 1 이상인 정수로 이루어져 있다.

수열 S에서 원하는 위치에 있는 수를 골라 최대 K번 삭제를 할 수 있다.

예를 들어, 수열 S가 다음과 같이 구성되어 있다고 가정하자.

수열 S : 1 2 3 4 5 6 7 8

수열 S에서 4번째에 있는 4를 지운다고 하면 아래와 같다.

수열 S : 1 2 3 5 6 7 8 

수열 S에서 최대 K번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구해보자.

입력

수열 S의 길이 N와 삭제할 수 있는 최대 횟수인 K가 공백으로 구분되어 주어진다.

두 번째 줄에는 수열 S를 구성하고 있는 N개의 수가 공백으로 구분되어 주어진다.

출력

수열 S에서 최대 K번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다.

제한

•  1≤N≤1,000,000
•  1≤K≤100,000
•  1≤ 원소의 값 ≤10^6

 

---

 

배울 점

투 포인터 풀이는 초기값 edge case 처리를 잘 해주자.

 

코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		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());
		}
		
		int ans = 0;
		int l = 0, r = 0;
		int tempK = (nums[0] % 2 == 1)? 1: 0;
		int temp = (nums[0] % 2 == 0)? 1: 0;
		ans = temp;
		while (true) {
			if (tempK > K) {
				if (nums[l++] % 2 == 0) {
					temp--;
				} else {
					tempK--;
				}
			} else {
				r++;
				if (r >= nums.length) break;
				if (nums[r] % 2 == 0) {
					temp++;
					if (temp > ans) ans = temp;
				} else {
					tempK++;
				}
			}
		}
		System.out.println(ans);
	}

}