[알고리즘] C++ 백준 22862 가장 긴 짝수 연속한 부분 수열 (large)

백준 22862

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

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

풀이 전 나의 생각

길이가 N인 수열이 주어질 때, K번 원소를 삭제한 수열에서

짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구해야 한다.

 

조건

- 1 <= N <= 1000000

- 1 <= K <= 100000

-1 <= 원소의 값 <= 10^6

 

과정

N과 K의 범위만 봐도 절대 단순 for문으로 풀면 안된다는 것을 알 수 있다.

따라서 O(n)의 속도로 풀 수 있는 투포인터 알고리즘을 사용하면 

제한 내에서 풀이가 가능하다.

 

과정은 다음과 같다.

1. 시작과 끝 포인터를 둔다.

2. 홀수가 K개를 초과할 때 까지 끝 포인터를 증가시켜 준다.

3. 홀수가 K개를 초과했다면 K보다 같거나 작아질 때 까지 시작 포인터를 증가시켜 준다.

 

예를 들어, 2, 4, 6, 7, 9, 10, 11, 12, 14 ,15의 수열이 있고 K가 2라고 가정하면

11 에서 홀수가 K개를 넘어서면서 현재 얻을 수 있는 최대 짝수길이가 만들어진다.

-> 7, 9를 제외한 (2, 4, 6, 10) 길이 4

 

다음으로 첫 홀수 7을 포함한 이전의 값들은 더 이상 볼 필요가 없기 때문에

홀수가 K보다 같거나 작아질 때 까지 시작 포인터를 증가시켜준다.

-> 이미 9와 11이 홀수로 자리잡고 있기 때문에 홀수 7의 이전 값은 고려하지 않는다. 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>

using namespace std;

int N, K, M;
vector<vector<int>>station(101001);
bool visited[101001];


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	vector<int>vec;

	int N, K;
	cin >> N >> K;

	for (int i = 0; i < N; i++)
	{
		// 수열 정보 저장
		int val;
		cin >> val;
		vec.push_back(val);
	}

	//시작 포인터, 끝 포인터, 홀수, 짝수, 최종값
	int start = 0, end = 0, odd = 0, even = 0, ans = 0;

	while (end < N)
	{
		// 현재 홀수 개수가 K보다 같거나 작다면 끝 포인터 증가
		if (odd <= K)
		{
			if (vec[end] % 2 != 0)
			{
				odd++;
			}
			else
			{
				even++;
				//짝수 최대 길이 갱신
				ans = max(even, ans);
			}
			end++;
		}
		//K보다 홀수 개수가 크다면 같거나 작아질 때 까지 시작 포인터 증가
		else
		{
			if (vec[start] % 2 != 0) odd--;
			else even--;

			start++;
		}
	}

	cout << ans;
}