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

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

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

문제

---

길이가 N인 수열 S가 있다. 수열 S는 1 이상인 정수로 이루어져 있다.

수열 S에서 원하는 위치에 있는 수를 골라 최대 K번 삭제를 할 수 있다.

예를 들어, 수열 S가 다음과 같이 구성되어 있다고 가정하자.

수열 S : 1 2 3 4 5 6 7 8

수열 S에서 4번째에 있는 4를 지운다고 하면 아래와 같다.

수열 S : 1 2 3 5 6 7 8 

수열 S에서 최대 K번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구해보자.

 

입력

---

수열 S의 길이 N와 삭제할 수 있는 최대 횟수인 K가 공백으로 구분되어 주어진다.

두 번째 줄에는 수열 S를 구성하고 있는 N개의 수가 공백으로 구분되어 주어진다.

 

출력

---

수열 S에서 최대 K번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다.

 

제한

---

•  1 ≤ N ≤ 1,000,000
•  1 ≤ K ≤ 100,000
•  1 ≤ 원소의 값 ≤10⁶ 

 

문제 풀이

---

투 포인터 문제.

처음에는 시작점(start)과 끝점(end)을 index 0으로 설정한 후 end가 가리키는 값이 홀수인지 짝수인지 확인하며 end를 증가시켜준다. start부터 end까지 홀수의 개수가 K보다 크다면 start를 증가시켜 start ~ end의 홀수의 개수가 K보다 크지 않도록 설정한다. start부터 end까지의 길이가 현재 얻을 수 있는 길이(이 중 홀수가 있다면 지울 수 있으므로 홀수의 개수만큼 빼주어야 한다.)이며, 이를 가장 긴 길이와 비교하며 가장 긴 길이를 업데이트 한다. 

 

#include <iostream>
using namespace std;

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

	int S, K;
	cin >> S >> K;
	int* arr = new int[S];
	int currentOddNum = 0;
	int start = 0;
	int end = 0;
	int length = 0;
	for (int i = 0; i < S; i++)
	{
		cin >> arr[i];
	}
	while (start < S)
	{
		if (end < S - 1)
		{
			if (arr[end] % 2 != 0)
			{
				currentOddNum++;
			}
			while (currentOddNum > K)
			{
				if (start > end)
				{
					break;
				}
				else
				{
					if (arr[start] % 2 != 0)
					{
						currentOddNum--;
					}
					start++;
				}
			}
			length = max(length, end - start + 1-currentOddNum);
			end++;
		}
		else
		{
			if (arr[end] % 2 != 0)
			{
				currentOddNum++;
			}
			if (currentOddNum <= K)
			{
				length = max(length, end - start + 1 - currentOddNum);
				break;
			}
			while (currentOddNum > K)
			{
				if (start > end)
				{
					break;
				}
				else
				{
					if (arr[start] % 2 != 0)
					{
						currentOddNum--;
					}
					start++;
				}
			}
			length = max(length, end - start + 1-currentOddNum);
		}
	}
	cout << length << "\n";
	return 0;
}