[백준 22862번 / Java] BOJ 22862 : 가장 긴 짝수 연속한 부분 수열 (large) (투포인터)

 

 

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

 

 

 

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

public class Main {
    public int solution(int N, int K, int[] S) {
        int answer = 0, lt = 0, cnt = 0;
        // 오른쪽 포인터가 배열의 끝까지 갈때까지만 진행
        for(int rt = 0; rt < N; rt++) {
            if(S[rt] % 2 != 0) cnt++; // 홀수라면 삭제 횟수 증가
			// 삭제 가능한 횟수를 초과하면 왼쪽 포인터를 오른쪽으로 옮기기
            while(cnt > K) {
                if(S[lt] % 2 != 0) cnt--;
                lt++;
            }
            // rt와 lt의 간격을 계산하고, 삭제한 홀수의 개수만큼 빼주기
            answer = Math.max(answer, rt - lt + 1 - cnt);
        }
        return answer;
    }

    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Main T = new Main();
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[] S = new int[N];

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

        System.out.println(T.solution(N, K, S));
    }

}

 

 

느낀 점 및 정리 ✍️

1. 코테 대비로 요즘 알고리즘 문제 풀 때 solution 메소드를 따로 생성하여 풀고 있다

2. 투 포인터 알고리즘을 활용하여 풀었다