codeforces #596 div2 B2 - TV subscribtions hard (투포인터)

https://codeforces.com/contest/1247/problem/B2

 

한국말 풀이가 있었으면 금방 넘어갔을 것 같은 문제. editorial에서 투포인트가 문제 풀이법이라고 해서, kks227님 블로그에 가서 관련 문제 풀어본 후 다시 풀어봤는데도 못품.

 

문제설명 : 

 배열크기 = 9,  요소종류 = 3, 범위 d = 3

 배열 : 3 3 3 2 2 2 1 1 1

로 주어졌을때 연속된 범위 만큼의 부분 배열에 포함된 종류의 최소를 구하는 문제이다.

위의 예제의 답은 1이 된다. ( 333 ''222'' 111 : 큰 따옴표로 표시한 부분배열일 때 정답을 알 수 있다.)

 

풀이:

 arr[0] ~ arr[d-1]에 포함된 각 요소의 개수를 미리 map에 저장해둔다. 

 arr[1]~arr[d], arr[2]~arr[d+1] .... arr[n-d-1]~arr[n-1] 구간을 차례로 순회하면서 처리해준다.

 ex) 처음 arr[1]~arr[d] 구간을 볼 땐, map에 arr[0]은 제외하고 arr[d]는 추가한 후, map에 저장된 요소의 개수를 mn에 갱신해 주면 된다.

 

코드

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int t; cin >> t;
	while (t--) {
		int n, k, d, arr[2000001];
		cin >> n >> k >> d;
		for (int i = 0; i < n; i++) cin >> arr[i];

		map<int, int> m1;
		for (int i = 0; i < d; i++) m1[arr[i]]++;
		int mSize = m1.size();
		for (int i = 0; i < n-d; i++) {
			m1[arr[i]]--;
			if (m1[arr[i]] == 0) m1.erase(arr[i]);
			m1[arr[i + d]]++;
			mSize = min((int)m1.size(), mSize);
		}
		cout << mSize << '\n';
	}
}