[BAEKJOON] 20922번 겹치는 건 싫어

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

20922번: 겹치는 건 싫어

문제조건

1. 같은 원소 k개 이하
2. 최장 연속 부분 수열의 길이

처음보는 문제유형이라 많이 당황했다,,

dp, LCS 등등 알고리즘을 고민해봤지만, 도저히 풀리는 그림이 나오지 않았다.

따라서 투 포인터라는 접근방식이 필요했다.

 

https://khu98.tistory.com/187

[백준OJ] 20922번 겹치는 건 싫어

이 글이 이해하는데 정말 도움을 많이 줬다. 감사합니다 ㅎㅎ

#include <iostream>
#include <vector>
using namespace std;

int n, k, cnt[100001];
vector<int> v;

int main(){
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		v.push_back(a);
	}
	int s = 0, e = 0,res = 0;
	while (s < n) {
		//정수가 k개 이하일때
		if (cnt[v[s]] != k) {
			cnt[v[s]]++;
			s++;
		}
		//정수가 k개이면 e포인터를 다음으로 이동 후, e포인터가 가리키던 정수 개수 -1
		else {
			cnt[v[e]]--;
			e++;
		}
		//k개 이하를 유지하며 최댓값 계속갱신
		res = max(res, s - e);
	}
	cout << res;
}