[백준] 20922번: 겹치는 건 싫어 with 투 포인터

투 포인터 활용 문제로 너무 좋은 문제라고 생각한다. 평소에 투 포인터를 풀긴 풀되 패턴화하지 못해서 실수가 잦았기 때문에 이 문제를 통해 패턴화하는 데 도움이 되었다.

 

연속 부분 수열에 대한 시작과 끝 구간을 지정한다. 주로 시작 구간을 움직일 때는 구간을 줄이는 일이기 때문에, 최대 개수가 늘어날 일도 없고, 갱신을 할 필요가 없다. 따라서 오른쪽 끝구간을 기점으로 값을 갱신하는 일을 수행하면 된다.

대신 이 때 늘어나기 전에 갱신을 해야 한다. 늘어난 후에는 그 때 순간에 최대 개수가 k를 초과하는 일이 발생할 수 있기 때문이다. 이 경우는 추가적인 iteration을 통해 시작점을 움직임으로써 구간을 줄이는 방식으로 처리될 예정이다.

 

여기서 어차피 숫자는 1 ~ 200,000 까지로 정해져 있으므로 unordered_map을 쓰지 않고, 일반 배열을 쓰는 방식으로 바꾸면 효율적이다.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
unordered_map<int,int> m;

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> vec(n);
	for(int i = 0;i < n;i++) {
		cin >> vec[i];
	}

	int start = 0;
	int end = 0;
	// 최대 길이와 그에 대한 시작, 끝점
	int max_len = 1;
	int max_start = 0;
	int max_end = 0;
	m[vec[0]]++;
	while(end < n) {
		if(m[vec[end]] > k) {
			m[vec[start]]--;
			start++;
		}
		else {
			if(end - start + 1 > max_len) {
				max_len = end - start + 1;
				max_start = start;
				max_end = end;
			}
			end++;
			m[vec[end]]++;
		}
	}

	cout << max_len << '\n';
}