사용한 것
- 배열에서 두 개의 포인터를 사용해 O(N)으로 탐색하기 위한 투포인터
풀이 방법
- 두 개의 포인터
l
, r
을 0부터 시작한다.
l
: 부분 수열 시작 지점
r
: 부분 수열 현재 지점
r
이 n
과 같아지면 최대 길이를 이미 구한 것이니 while 문을 종료한다.
- 홀수를 제거할 기회가 남은 경우
- 홀수면 제거할 기회를 사용한다.
r
을 증가시키고 maxLen
을 갱신한다.
- 홀수를 제거할 기회가 없지만 이번 수가 짝수인 경우
- 홀수를 제거할 기회가 없고 이번 수가 홀수인 경우
l
이 홀수라면 ct
를 감소시킨다.
l
을 증가시킨다.
코드
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] line = br.readLine().split(" ");
int n = Integer.parseInt(line[0]);
int k = Integer.parseInt(line[1]);
boolean[] arr = new boolean[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
int num = Integer.parseInt(st.nextToken());
arr[i] = num % 2 == 0;
}
int maxLen = 0;
int l = 0;
int r = 0;
int ct = 0;
while (r < n) {
if (ct < k) {
if (!arr[r]) {
ct++;
}
r++;
maxLen = Math.max(r - l - ct, maxLen);
} else if (arr[r]) {
r++;
maxLen = Math.max(r - l - ct, maxLen);
} else {
if (!arr[l]) {
ct--;
}
l++;
}
}
System.out.println(maxLen);
}
}