알고리즘 연습/백준
[투포인터 BOJ20922 BOJ22862]
_h.j
2024. 4. 20. 15:47
728x90
BOJ 20922 겹치는 건 싫어
O(N)
#include <iostream>
#define MAX_N 200000
#define MAX_A 100001
using namespace std;
int N, K;
int arr[MAX_N];
int cnt[MAX_A];
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> K;
for (int i = 0; i < N; i++)
cin >> arr[i];
int ans = 1;
int left = 0, right = 0;
while (right < N) {
int num = arr[right];
if (cnt[num] < K) {
cnt[num]++;
}
else {
while (arr[left] != num) {
cnt[arr[left]]--;
left++;
}
left++; //right로 수가 대체됨.
}
right++;
ans = max(ans, right - left);
}
cout << ans;
return 0;
}
BOJ 22862 겹치는 건 싫어
#include <iostream>
#define MAX_N 1000000
using namespace std;
int N, K;
int arr[MAX_N];
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> K;
for (int i = 0; i < N; i++)
cin >> arr[i];
int ans = 0;
int cnt = 0;//홀수 개수
int left = 0, right = 0;
while (right < N) {
int num = arr[right];
if (num % 2) {
if (cnt >= K) {
while (arr[left]%2 == 0) {
left++;
}
left++;
}
else cnt++;
}
right++;
ans = max(ans, right - left - cnt);
}
cout << ans;
return 0;
}
728x90