[BOJ/C++] 20922 겹치는 건 싫어 : Two Pointer

문제

https://www.acmicpc.net/problem/20922

풀이

🧠연속 수열의 합 ➡️투포인터 ➡️같은 방향 진행

cnt 배열에서 최댓값을 찾을 필요없이 cnt[end]를 ++했으니까 cnt[end]랑 k를 비교하면 됨
(처음에 이거 때문에 시간초과 남)

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int cnt[100001];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, k;
	int ans = 0;
	vector<int> v;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		v.push_back(tmp);
	}

	//Two Pointer
	int end = 0;
	for (int start = 0; start < n; start++) {
		while (end < n && cnt[v[end]] < k) {
			cnt[v[end]]++;
			end++;
		}
		ans = max(ans, end - start);

		if (end == n)	break;

		cnt[v[start]]--;
	}

	cout << ans;

	return 0;
}