백준/투포인터
겹치는건 싫어
연구하는개발자
2021. 4. 12. 21:22
728x90
20922번: 겹치는 건 싫어
홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열
www.acmicpc.net
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<deque>
#include<math.h>
#include<cmath>
using namespace std;
int main() {
int n, k;
cin >> n;
cin >> k;
vector<int>v(n);
for(int i = 0; i < n; i++) {
cin >> v[i];
}
int s = 0;
int e = 0;
map<int,int>m;
int maxlen = 0;
m[v[s]]++;
while (s <= e) {
if (m[v[e]] > k) {
if (maxlen < (e - s)) {
maxlen = e - s;
}
m[v[s]]--;
s++;
}
else {
e++;
if (e >= n) {
if (maxlen < (e - s)) {
maxlen = e - s;
}
break;
}
m[v[e]]++;
}
}
cout << maxlen;
}