[백준] Gold V. 가장 긴 짝수 연속한 부분 수열 (large)

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

 

사용 알고리즘

• 투 포인터

 

풀이

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

public class Main {
    /*
        1. 원소를 순회하며 홀수인 경우 삭제한다.
        2. 삭제 횟수가 k번 초과한 경우, 루프를 빠져나와 max값을 갱신한다.
     */
    static int n, k;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        int [] arr = new int[n];

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

        int hi = 0;
        int delete = 0;
        int total_delete = 0;
        int max = 0;

        for(int lo = 0; lo < n; lo++) {
            while(hi < n && delete <= k) {
                if (arr[hi] % 2 != 0) {
                    delete++;
                    total_delete++;
                }
                hi++;
            }

            if (hi == n) break;

            int len = hi - lo - delete;

            max = Math.max(max, len);
            if (arr[lo] % 2 != 0) {
                delete--;
            }
        }

        if (total_delete <= k) { // 전체 순회했음에도 삭제 횟수가 k보다 작을 때
            System.out.println(n - total_delete);
        }
        else System.out.println(max);
    }
}

 

회고

 

배열을 순회하면서 홀수인 원소를 찾을 때, delete를 증가시켜주고 k를 초과한 경우 루프를 빠져나온다.

 

부분 수열의 길이를 구하는 방법은 hi (현재 위치) - lo (시작점) - delete(삭제한 홀수 개수)로 계산해주었다. 

 

total_delete 변수를 추가한 이유는 

6 2
2 4 6 8 8 6

 

위 예제에서 홀수가 없기 때문에 while문을 빠져나오지 못해 max값을 갱신하지 못하고, 0을 출력한다.

 

 

백준에서 찾아본 반례도 다 통과했는데 계속 틀렸다고 나와서 힘들었다.

그런데, 이 부분에서 차이가 있었다.

 

이전 코드

delete--;

 

수정한 코드

if (arr[lo] % 2 != 0) {
    delete--;
}

 

 

결국, 시작점을 어떻게 조작하는지가 중요하다

 

이전 코드는 시작점이 증가할 때마다 delete를 감소시킨다.

 

수정한 코드는 시작점의 값이 홀수일때만 delete를 감소시킨다. 

 

이전 코드는 홀수를 제거하지 않았어도 감소시켜 주기 때문에 홀수 갯수를 정확히 세지 못할 수도 있다.