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

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

20922번: 겹치는 건 싫어

---

 

-풀이-

먼저, st포인터를 앞으로 보내며, st포인터가 가리키고있는 원소의 개수가 k개가 아니라면, 해당원소의 개수를 +1 증가시키고 st를 앞으로 전진시킨다. 만약 해당원소가 k개인 원소를 가리키고있다면, end포인터를 앞으로 전진시키며 end포인터가 가리키고있는 원소의 개수를 -1 해가면서 전진시킨다. end를 전진시키다가 st가 가리키고 있는 원소를 하나 감소시키면, st포인터가 앞으로 갈 수 있게 되므로, st가 마지막 원소를 검사하고 다음으로 넘어가면 종료를 시키면된다.

 

이때 갱신시킬 데이터는 수열의 길이이므로, st-end를 해주면된다.

 

예시 1번으로 설명을 해보겠다.

 

 

1. 초기상태.

 

 

2. ST포인터가 가리켰던 3의 개수가 0이였으므로, 1을 증가시키고 한칸 전진. 그런뒤 RESULT갱신

 

 

3. ST포인터가 가리켰던 2의 개수가 0개였으므로, 1을 증가시키고 한칸 전진한뒤 RESULT갱신

 

 

4. ST포인터가 가리켰던 5의 개수가 0이였으므로, 1을 증가시키고 한칸 전진한 뒤 RESULT갱신

 

 

5.ST포인터가 가리켰던 5의 개수가 1이였으므로, 1을 증가시키고 한칸 전진한 뒤 RESULT갱신

 

 

 

6. ST포인터가 가리켰던 6의 개수가 0이였으므로, 1을 증가시키고 한칸 전진한 뒤 RESULT갱신

 

 

7. ST포인터가 가리켰던 4의 개수가 0이였으므로, 1을 증가시키고 한칸 전진한 뒤 RESULT갱신

 

 

8. ST포인터가 가리켰던 4의 개수가 1이였으므로, 1을 증가시키고 한칸 전진한 뒤 RESULT갱신

 

9. ST포인터가 가리키고있는 5의 개수가 2이므로, (K==2이기 때문에 전진X) END가 가리키고있던 3을 1 감소시키고 한칸 전진

 

10. ST포인터가 가리키고있는 5의 개수가 2이므로, END가 가리키고있던 2를 1 감소시키고 한칸 전진

 

 

11.ST포인터가 가리키고있는 5의 개수가 2이므로, END가 가리키고있던 5를 1 감소시키고 한칸 전진

 

 

12. ST포인터가 가리키고 있던 5의 개수가 1이므로, 1을 증가시키고 한칸 전진

 

 

13. ST포인터가 가리키고 있던 7의 개수가 0이므로, 1을 증가시키고 한칸 전진. ST가 N이 되었으므로 종료.

 

-시간복잡도-

O(N)이 된다.

 

-코드-

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

int arr[200000];
int cnt[100001];
int n, k;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> n >> k;
	for (int i = 0; i < n; i++) cin >> arr[i];
	
	int st = 0;
	int end = 0;
	int result = 0;
	while (st < n) {
		if (cnt[arr[st]] != k) {
			cnt[arr[st]]++;
			st++;
		}
		else {
			cnt[arr[end]]--;
			end++;
		}
		result = max(result, st - end);
	}
	cout << result << "\n";
	return 0;
}