[BOJ/C++] 22862: 가장 긴 짝수 연속한 부분 수열(large)

🏅 Gold 5

✏️ 1차 솔루션

⭐️ Two Pointer

1. start 포인터를 첫번째 짝수, 시작 포인터와 짝수 사이에 홀수 개수가 K 이하인 짝수를 end 포인터로 지정
2. 위 조건 만족하는 한해서 포인트 옮겨가며 짝수 거리 갱신

🚨 trouble

시작 포인터와 끝 포인터를 무조건 짝수로 하다보니 풀이가 난잡해짐

✏️ 최종 솔루션

⭐️ Two Pointer
⭐️ 짝수가 아예 없는 경우도 존재하기 때문에 일딴 start, end 포인터를 동일하게 0 으로 정의하여 시작

1. 홀수 개수가 k 를 초과하면 start 포인터를 옮겨주기
2. 홀수 개수가 K 이하이면 end 포인터를 옮겨주기
3. 포인터를 옮긴 후에도 홀수 개수가 k 이하이면 현재 구간의 거리 갱신

📌 self feedback

Two Pointer 풀이를 할 때는 구간을 미리 정의해주기 애매하면 start, end 를 모두 0 으로 정의하고 end 포인터를 우선적으로 이동하되 더 이상 이동할 수 없는 경우라면 start 포인터를 옮겨주는 방식으로 두 포인터를 옮겨가며 최적의 구간을 탐색해야 함

✏️ 최종 code

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, k;
    cin >> n >>k;
    vector<int> num(n);
    for(int i=0;i<n;i++) {
        cin >> num[i];
    }
    
    int st=0,end=0,cnt=0,ans=0;
    while (end<n) {
        if(cnt>k) {
            if(num[st]%2==1) cnt--;
            st++;
        }
        else {
            if(num[end]%2==1) cnt++;
            end++;
        }
        
        if(cnt<=k) ans=max(ans,end-st-cnt);
    }
    
    cout << ans << endl;
    
}