[백준] 20922번 - 겹치는 건 싫어 / C++

문제

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

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

 

입력

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

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

 

출력

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

 

코드

#include <iostream>
#include <cstring>

using namespace std;

int N;
int K;
int num[200001];
int cnt[100001];

int main()
{
	int i, s, e;
	int res = 0;
	bool flag;
	
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> K;
	for (i = 1; i <= N; i++)
	{
		cin >> num[i];
	}
	s = 1;
	e = 1;
	while (s <= e && e <= N)
	{
		while (e <= N)
		{
			if (cnt[num[e]] == K)
				break;
			cnt[num[e++]]++;
		}
		res = max(res, e - s);
		flag = true;
		while (s < e && flag)
		{
			if (cnt[num[s]] == K)
				flag = false;
			cnt[num[s++]]--;
		}
	}
	cout << res << "\n";
	return 0;
}

 

s는 부분 수열의 시작 인덱스이고 e는 부분 수열의 끝 인덱스이다. 첫 번째 정수부터 시작해 최장 연속 부분 수열의 길이를 구한다. 

부분 수열에 포함되는 num[e]의 개수가 K개 미만이면 num[e]를 추가할 수 있다. 끝 인덱스인 e를 1만큼 증가시켜 부분 수열의 범위를 한 칸 늘려준다. 만약 num[e]의 개수가 이미 K개라면 num[e]를 부분 수열에 포함시킬 수 없으므로 while문을 빠져나온다.

while문을 빠져나온 뒤 시작 인덱스는 s, 끝 인덱스는 e이다. 이때 e는 부분 수열에 포함되지 못했으므로 부분 수열의 범위는  [s, e)이다. 따라서 부분 수열의 길이는 (e - s)이고, 이 값을 사용해 최대 길이를 갱신한다.

이제 두 번째 while문에서 K개 존재하는 원소를 찾을 때까지 부분 수열의 범위를 줄인다. K개 존재하는 원소 중 하나를 제외시켜야 num[e]를 추가할 수 있는 가능성이 생기기 때문이다.

이 과정을 전체 수열에 대해 반복하여 최장 연속 부분 수열의 길이를 구한다.

 

링크

20922번: 겹치는 건 싫어

inbdni/Baekjoon