본문 바로가기

백준/투포인터

겹치는건 싫어

728x90

www.acmicpc.net/problem/20922

 

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