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;
}
'백준 > 투포인터' 카테고리의 다른 글
부분합 - 1806번 (0) | 2021.09.01 |
---|---|
두수의 합 - 3273번(Java) (0) | 2021.09.01 |
두 용액 (0) | 2021.04.11 |
구간 합 구하기4 (0) | 2021.04.08 |
배열합치기 (0) | 2021.04.08 |