백준 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번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다.

 

 

문제 이해하기

input:

8 2

1 2 3 4 5 6 7

output:

3

int h = 0;  //h 인덱스

int t = 0;  //t 인덱스

int cnt = 0;  //홀수 개수

풀이

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

public class SubSeq {

	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());
	     StringBuilder sb = new StringBuilder();
	     
	     int max = 0;
	     
	     int n = Integer.parseInt(st.nextToken());
	     
	     int k = Integer.parseInt(st.nextToken());
	     
	     int[] get = new int[n];
	     
	     st = new StringTokenizer(br.readLine());
	     
	     for(int i=0; i<n; i++) {
	    	 get[i] = Integer.parseInt(st.nextToken());
	     }
	     
	     int head = 0;  //시작 인덱스
	     int tail = 0;  //꼬리 인덱스
	     int cnt = 0;   //홀수의 개수
	     
	     while(true) {
	    	 if(cnt>k) {
	    		 if(get[head]%2==1) {
	    			 //get[head]가 홀수이면 head가 옮겨질 때 cnt--
	    			 cnt--;
	    		 }
	    		 head++;
	    	 }else if(tail==n) {
	    		 //tail이 n과 같아지면 끝
	    		 break;
	    	 }else {
	    		 if(get[tail]%2==1) {
	    			 //get[tail]이 홀수이면 tail이 1 커지면 cnt++
	    			 cnt++;
	    		 }
	    		 tail++;
	    	 }
	    	 if(cnt<=k) {
	    		 //전체 짝수 부분수열의 길이는 tail-head-(홀수의 개수)
	    		 max = Math.max(max, tail-head-cnt);
	    	 }
	     }
	     
	     sb.append(max);
	     bw.write(sb.toString());
	     bw.flush();
	     bw.close();
	}

}