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

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

20922번: 겹치는 건 싫어

투포인터를 이용해서 할 수 있는 문제이다.

 

1. 맨 처음에는 시작점과 끝점을 둘다 idx 0으로 둔다 (왼쪽 포인터를 st, 오른쪽 포인터를 en이라 칭하겠음)

 

2. 조건에 맞게 en이 N보다 작으면서 아직 K개 이하로 등장했다면 오른쪽 포인터를 오른쪽으로 옮겨준다. 

이걸 while반복문으로 조건에 걸릴 때까지 늘려준다.

while(en < N && visited[v[en]] < K) {
	visited[v[en]]++;
    en++;
}

라고 나타낼 수 있다.

 

3. 조건식에 걸리면 while문에 빠져나오게 되는데 while문에서 나오는 경우는 2가지가 존재한다.

   (1) 오른쪽 포인터가 배열을 모두 확인하고 배열의 크기 외부로 포인터가 옮겨갔을 경우

   (2) 중복되는 수가 K개 이상인 걸 발견했을 때

만약 1번의 경우일 때는 그 길이를 확인해주고 최대길이면 최신화 해주고 바로 프로그램을 끝내고, 2번일 경우에는 아직 오른쪽 포인터가 확인해야할 원소가 존재하므로 왼쪽 포인터를 오른쪽으로 한칸옮겨준다. 이 때 왼쪽 포인터가 가리키는 수의 개수는 -1개 해주어야 한다.

 

#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <bitset>
#define INF 987654321
#define CUNLINK ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
#define ll long long
#define endl '\n'

using namespace std;

int visited[100002];

int main() {
	CUNLINK;
	int N, K, answer = -1;
	cin >> N >> K;
	vector<int> v(N);
	for (int i = 0; i < N; i++) cin >> v[i];

	int en = 0;
	int st = 0;
	for (int st = 0; st < N; st++) {
		while (en < N && visited[v[en]] < K) {
			visited[v[en]]++;
			en++;
		}
		answer = max(answer, en - st);
		if (en == N) break;
		visited[v[st]]--;
	}
	cout << answer << endl;

	return 0;
}