[G5] 백준 22862번 가장 긴 짝수 연속한 부분 수열 (large) C++ 투 포인터

리뷰

 

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

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

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• s : 수열 정보를 저장할 배열
• n : 수열의 길이를 저장할 변수
• k : 삭제 가능한 최대 원수 개수를 저장할 변수

 

함수

없음

 

 

문제풀이

1. n, k값을 입력 받고, n개의 원소를 입력 받아 s배열을 초기화한다.
2. 변수 l, r, c, len, ans를 모두 0으로 초기화한다.
3. r이 n미만일 경우를 조건으로 하는 while루프를 수행한다.
4. s[r]이 홀수일 경우 c를 증가시키고, 짝수일 경우 len을 증가시킨다.
5. c가 k보다 클 경우 s[l]이 홀수라면 c를 감소시키고, 짝수일 경우 len을 감소시킨 후 l을 증가시킨다.
6. ans를 len과 비교하여 더 큰 값을 ans에 저장하고, r을 증가시킨다.
7. while루프가 종료된 후 ans에 저장된 값을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 두 포인터를 배열의 왼쪽에서부터 시작하여 탐색을 수행한다.
2. c를 통해 삭제시킨 원소의 개수를 추적하고, len을 통해 현재까지의 연속된 짝수의 개수를 추적한다.
3. c가 k보다 커졌을때에만 l포인터를 증가시키고, r은 매 루프마다 증가시킨다.

 

정답 코드

#include<iostream>
using namespace std;

const int N = 1e6;
int s[N];
int n, k;

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

	cin >> n >> k;
	for (int i = 0; i < n; ++i) cin >> s[i];

	int l = 0, r = 0, c = 0, len = 0, ans = 0;
	while (r < n) {
		if (s[r] % 2) ++c;
		else ++len;
		
		while (c > k) {
			if (s[l] % 2) --c;
			else --len;
			++l;
		}

		ans = max(ans, len);
		++r;
	}
	cout << ans;
}