[G5] 가장 긴 짝수 연속한 부분 수열 : 22862 : Java - 투 포인터

1. 💎 문제

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

 

 

 

2. 🤔 어떻게 풀까

무조건 삭제를 해야하므로(자세히 보면 삭제는 선택 사항이었음,,,) 무엇을 삭제할지 생각했을 때 홀수를 우선적으로 삭제해야 한다. 짝수 사이에 있는 홀수를 뺴줘야 이어질 수 있기 때문이다. 그리고 범위안에는 오직 최대 k개의 홀수만 있어야 하므로 홀수가 k개가 넘어가는 시점에서 걸러주는 작업을 하기로 했다.

그러므로 짝수와 홀수의 경우로 나눠 풀자고 생각했고, 투 포인터를 적용하여 `end`로는 수를 더하거나 탐색하고 `start`로는 수를 빼준다.

 

 

3. 💡 로직

1. 수열 입력

수열을 `nums`배열에 입력 받는다.

	int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

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

 

2. 최단 짝수 수열 길이 구하기

수열에 차례대로 접근하여 홀수와 짝수를 판단한다. 짝수이면  수열의 길이를 더하록 고 홀수이면 홀수의 개수를 더한다. 만약 홀수의 개수가 k개를 넘어갔다면 수열의 범위를 수정 한다.

	int start =0; int end = 0;
        int length = 0; int odd_count =0;

        // 홀수이면 k++, 짝수이면 count++,
        while(end < N){
            if(nums[end] %2 ==0){
                length++;
            }
            else{
                odd_count++;
            }

            end++;
            result = Math.max(result, length);
            if(odd_count <= K)
                continue;
        }

수정은 `start` 인덱스가 루프를 돌다 처음 홀수를 만날 떄 중단하며, 루프를 돌다 짝수를 만나면 짝수의 수만큼 수열의 길이에서 뺀다. 이때 수열의 길이을 감소하는 상황이 생기기 때문에 수정 작업 전에 결과를 저장한다. 

{
	result = Math.max(result, length);

            while(true){
                if(nums[start] %2 != 0){
                    odd_count--;
                    start++;
                    break;
                }
                else{ // 짝수
                    start++;
                    length--;
                }

            }          
 }

 

 

4. 📄 전체 코드

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

public class BOJ_가장긴짝수연속한부분수열 {

    static BufferedReader br;
    static BufferedWriter bw;

    public static void main(String [] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        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 [] nums = new int[N+1];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            nums[i] = Integer.parseInt(st.nextToken());
        }

        int start =0; int end = 0;
        int length = 0; int odd_count =0;
        int result = 0;

        // 홀수이면 k++, 짝수이면 count++,
        while(end < N){
            if(nums[end] %2 ==0){
                length++;
            }
            else{
                odd_count++;
            }

            end++;
            result = Math.max(result, length);
            if(odd_count <= K)
                continue;

            // 초과 -가장 처음 만나는 홀수 제외
            while(true){
                if(nums[start] %2 != 0){
                    odd_count--;
                    start++;
                    break;
                }
                else{ // 짝수
                    start++;
                    length--;
                }

            }
        }

        System.out.println(result);
    }
}