[백준 / 골드5] 22862 가장 긴 짝수 연속한 부분 수열 (large) (Java)

문제 보기

사용한 것

• 배열에서 두 개의 포인터를 사용해 O(N)으로 탐색하기 위한 투포인터

풀이 방법

• 두 개의 포인터 l, r을 0부터 시작한다.
  • l : 부분 수열 시작 지점
  • r : 부분 수열 현재 지점
• r이 n과 같아지면 최대 길이를 이미 구한 것이니 while 문을 종료한다.
• 홀수를 제거할 기회가 남은 경우
  • 홀수면 제거할 기회를 사용한다.
  • r을 증가시키고 maxLen을 갱신한다.
• 홀수를 제거할 기회가 없지만 이번 수가 짝수인 경우
  • r을 증가시키고 maxLen을 갱신한다.
• 홀수를 제거할 기회가 없고 이번 수가 홀수인 경우
  • l이 홀수라면 ct를 감소시킨다.
  • l을 증가시킨다.

코드

public class Main {

    public static void main(String[] args) throws IOException {
        // 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int k = Integer.parseInt(line[1]);
        boolean[] arr = new boolean[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(st.nextToken());
            arr[i] = num % 2 == 0;
        }

        // 투포인터
        int maxLen = 0;
        int l = 0;
        int r = 0;
        int ct = 0;
        while (r < n) {
            if (ct < k) {
                if (!arr[r]) {
                    ct++;
                }
                r++;
                maxLen = Math.max(r - l - ct, maxLen);
            } else if (arr[r]) {
                r++;
                maxLen = Math.max(r - l - ct, maxLen);
            } else {
                if (!arr[l]) {
                    ct--;
                }
                l++;
            }
        }

        System.out.println(maxLen);
    }
}