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

오늘은 백준 22862번 "가장 긴 짝수 연속한 부분 수열 (large)" 문제를 해결한 방법과 생각의 흐름을 공유하고자 합니다!

 

이 문제의 경우에는 solved에서 제공하는 난이도 기준 골드 5에 위치하고 있습니다! 
난이도로 보면... 크게 어렵진 않을 것 같은데 고려할 사항들이 조금은 있습니다!

문제 분석:
이 문제는 주어진 수열에서 최대 K개의 홀수를 제거하여 얻을 수 있는 가장 긴 짝수 연속 부분 수열의 길이를 찾는 것입니다. 수열의 길이가 최대 1,000,000이므로 효율적인 알고리즘이 필요합니다.

접근 방법:
이 문제를 해결하기 위해 수열의 길이를 고려한다면, O(N)에 해당하는 시간복잡도로 풀어야 한다고 생각했기 때문에, 투 포인터(Two Pointers) 기법을 사용했습니다.

구현 과정:
1. 입력 처리 및 초기화:
   - 수열의 길이 N과 제거할 수 있는 홀수의 최대 개수 K를 입력받습니다.
   - 수열을 벡터에 저장하고, 짝수가 하나라도 있는지 확인합니다.

2. 예외 처리:
   - 짝수가 없는 경우, 결과는 0입니다.
   - 수열의 길이가 1인 경우, 그 수가 짝수면 1, 홀수면 0을 출력합니다.

3. 투 포인터 알고리즘 구현:
   - 왼쪽 포인터(l)와 오른쪽 포인터(r)를 이용하여 수열을 탐색합니다.
   - cnt 변수로 현재 구간에서 제거할 수 있는 홀수의 개수를 관리합니다.
   - 오른쪽 포인터를 이동시키며 짝수를 만나면 계속 전진하고, 홀수를 만나면 cnt를 감소시킵니다.
   - cnt가 0 미만이 되면, 왼쪽 포인터를 이동시키며 홀수를 제거합니다.

   - 왼 쪽 포인터 이동시 현재의 왼 쪽 포인터가 짝수를 가르키고 있다면 cnt를 증가시키지 않습니다.
   - 각 단계에서 현재 구간의 짝수 연속 부분 수열의 길이를 계산하여 최대값을 갱신합니다.

4. 결과 출력:
   -  찾은 최대 길이를 출력합니다.

코드 구현:

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N, K, res;
vector<int> v;
bool flag{false};

void TP() {
    int l{0}, r{1}, cnt{K};
    if (v[l] % 2 && v[r] % 2) {
        cnt -= 2;
    } else if (v[l] % 2 || v[r] % 2) {
        cnt--;
    }
    while(l<N && r<N) {
        if(cnt>=0) {
            res = max(res, r - l + 1 + cnt - K);
        }
        if(v[r+1]%2==0) {
            r++;
            continue;
        }
        if(cnt<=0) {
            if (v[l] % 2) {
                cnt++;
            }
            l++;
            continue;
        }
        r++;
        if (v[r] % 2) {
            cnt--;
        }
    }
}

void Solve() {
    if (!flag) {
        cout << 0 << '\n';
        return;
    }
    if (N == 1) {
        if (v[0] % 2) {
            cout << 0 << '\n';
        } else {
            cout << 1 << '\n';
        }
        return;
    }
    TP();
    cout << res << '\n';
}

void Init() {
    cin >> N >> K;
    v.resize(N+1);
    for (int i = 0; i < N; i++) {
        cin >> v[i];
        if (v[i] % 2 == 0) {
            flag = true;
        }
    }
}

int main() {
    cin.tie(nullptr)->ios_base::sync_with_stdio(false);
    Init();
    Solve();
    return 0;
}

주요 포인트:
1. 투 포인터 기법을 사용하여 O(N) 시간 복잡도로 문제를 해결했습니다.
2. 예외 케이스(짝수가 없는 경우, 수열의 길이가 1인 경우)를 먼저 처리하여 코드의 안정성을 높였습니다.
3. cnt 변수를 통해 현재 구간에서 제거할 수 있는 홀수의 개수를 효율적으로 관리했습니다.

결론:
이 문제는 양 끝단에서 시작하는 것이 아닌 한 쪽에서 나란히 시작하는 투 포인터 알고리즘의 좋은 예시입니다. 큰 크기의 수열을 효율적으로 처리해야 하는 상황에서 투 포인터 기법이 매우 유용함을 알 수 있습니다. 또한, 예외 케이스를 고려하는 것의 중요성도 다시 한 번 느낄 수 있을만한 문제입니다!

이상으로 백준 22862번 문제 해결에 대한 분석을 마치겠습니다!!

이 글이 여러분의 알고리즘 학습에 도움이 되었기를 바랍니다!

혹시 문제와 관련해서 궁금한 점이나 오타 등은 댓글 남겨주세요!