[알고리즘] C++ 백준 20922 겹치는 건 싫어

백준 20922

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

20922번: 겹치는 건 싫어

풀이 전 나의 생각

수열 N이 주어질 때, 원소가 K개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구해야 한다.

 

조건

- (1 <= N <= 200000)

- (1 <= K <= 100)

- a1, a2... (1 <= ai <= 100000)

 

과정

N이 20만이기 때문에 단순 for문으로 문제 풀이를 접근한다면

엄청난 계산 횟수로 시간 제한을 맞추지 못한다.

-> O(n^2) 만 되어도 20만 * 20만 = 400억

 

따라서 투 포인터 알고리즘을 사용하여 풀이를 진행해야 한다.

 

과정은 다음과 같다.

 

1. 시작 포인터와 끝 포인터를 설정해준다.

2. 현재 끝 포인터의 원소가 K개 미만 이라면 끝 포인터와, 구하고자 하는 수열의 길이를 늘려준다.

3. 현재 끝 포인터의 원소가 K개 이상 이라면 K개 미만이 될 때 까지 시작 포인터를 증가 시켜준다.

ex) 3 2 5 5 6 4 4 5 까지 선택된 부분 수열이 있다면 현재 끝 포인터 5는 이미 원소가 2개 포함되어 있기 때문에
2개 이하가 될 때 까지 즉, 4번 째 순서의 5까지 시작포인터를 증가 시켜주며 이전에 앞서 선택된 원소들을
제거해준다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>

using namespace std;

int arr[200001];
int visited[200001];

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

	int N, K, end = 0, start = 0, len = 0, ans = 0;

	cin >> N >> K;

	for (int i = 0; i < N; i++)
	{
		//수열 저장
		cin >> arr[i];
	}

	while (end < N)
	{
		// 끝 포인터의 원소가 K개 미만 이라면 끝 포인터, 현재 연속된 부분 수열 길이 증가
		if (visited[arr[end]] < K)
		{
			visited[arr[end]]++;
			end++;
			len++;

			ans = max(ans, len);
		}
		// 이미 끝 포인터의 원소가 K개 일 때 시작 포인터를 증가 시켜주며 앞서 선택된 원소 삭제 및 길이 감소
		else
		{
			visited[arr[start]]--;
			len--;
			start++;
		}
	}

	cout << ans;
}