[C++] 백준 20922 : 겹치는 건 싫어

 

 

 

문제

홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 K개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다.

 100,000 이하의 양의 정수로 이루어진 길이가 N인 수열이 주어진다.  이 수열에서 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.

 

 

 

입력

첫째 줄에 정수 N(1 ≤ N ≤ 200000)과 K(1 ≤ K ≤ 100)가 주어진다.

둘째 줄에는 a1, a2, ... , an이 주어진다. (1 ≤ ai ≤ 100000)

 

 

 

출력

조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다.

 

 

---

 

 

문제 해결

 

이중 for문을 이용한 브루트포스 알고리즘은 탐색 범위를 나름대로 최적화 후 제출해봤지만 아쉽게도 실행 시간 초과가 발생했습니다.

따라서 투 포인터를 이용하여 해결 가능합니다.

 

start와 end라는 두 개의 포인터가 입력된 수열 ary를 순차적으로 탐색하게 됩니다.

 

end ≤ N를 만족하면 다음 내용을 반복합니다.

1. 먼저 end가 ary의 첫 원소부터 이동합니다.

2. 만약 end가 탐색하는 값 t의 개수가 K개보다 커지면, start는 t의 개수가 K개보다 작거나 같아질 때까지 이동합니다.

3. end - start +1개와 현재 최대값을 비교하여 최대값을 갱신합니다.

 

 

 

코드

#include <iostream>
using namespace std;

int ans, n, k, ary[200001], cnt[100001];

int main() {
	cin >> n >> k;

	for (int i = 1; i <= n; i++) scanf("%d", ary + i);

	int start = 1, end = 0;

	while (end < n) {
		end++;
		cnt[ary[end]]++;

		if (cnt[ary[end]] > k)
			while (cnt[ary[end]] > k) {
				cnt[ary[start]]--;
				start++;
			}
		
		ans = max(ans, end - start + 1);
	}

	cout << ans;
}