20922 겹치는 건 싫어

www.acmicpc.net/problem/20922

20922번: 겹치는 건 싫어

투포인터라는 방법을 응용하면 쉽게 풀 수 있는 문제이다.

접근은 다음과 같다.

맵을 이용하여 중복을 체크한다.

1. 탐색의 처음 부분을 두 개의 포인터가 가리킨다.

2. 끝 부분의 포인터가 이동하면서 중복 개수가 K개를 초과하면, 시작 부분의 포인터를 다음으로 이동시키고 해당 값을 한 개 줄인다.

3. K개 이하가 될 때까지 2를 반복한다.

4. 배열의 길이 N까지 탐색을 마치면 종료한다.

 

고찰 : 놓쳤던 부분은 K개를 초과하면 이전에 저장했던 모든 정보들을 다 날려버렸기 때문에 틀렸었다. 따라서 맨 앞에서 찾았던 정보를 하나씩 지우면서 접근해야 올바른 방법이다.

정답코드

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
unordered_map<int, int> um;
int N, K;
int main()
{
	cin >> N >> K;
	vector<int> v(N, 0);
	for (int i = 0; i < N; i++)
		scanf("%d", &v[i]);
	int s = 0, e = 0;
	int answer = 0, len = 0;
	while (e < N) {
		int num = v[e];
		um[num]++;
		if (um[num] > K) {
			um[num]--;
			um[v[s]]--;
			s++;
		}
		else {
			e++;
			len = e - s;
			answer = max(len, answer);
		}
	}
	printf("%d\n", answer);
	return 0;
}