ABC_194_E - Mex Min

[zeikar]

Problem link

https://atcoder.jp/contests/abc194/tasks/abc194_e

Problem Summary

0≤i≤N−M 범위에서 mex의 최솟값을 구하는 문제.

• Mex(x1...xk): x1...xk 에 속하지 않는 가장 작은 0이상의 정수.

Solution

아주 간단하게 생각해보면 쉽게 풀린다.

Ai의 최대 범위가 N이므로 0부터 N까지의 수를 맵에 넣어 두고 범위 안에서 Ai의 값이 나오면 맵에서 제거, Ai값이 없어지면 맵에 추가하는 방식으로 할 수 있다.

즉, 속하지 않는 가장 작은 0이상의 정수 (Mex)를 맵 형태로 계속 유지하는 것.

Source Code

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

int a[1500000];
int cnt[1500001];

int main() {
	int n, m;
	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}

	map<int, bool> notOccurred;
	for (int i = 0; i <= n; i++)
	{
		notOccurred[i] = true;
	}

	for (int i = 0; i < m; i++)
	{
		if (cnt[a[i]] == 0)
		{
			notOccurred.erase(a[i]);
		}

		cnt[a[i]]++;
	}

	int ans = notOccurred.begin()->first;
	for (int i = m; i < n; i++)
	{
		if (cnt[a[i]] == 0)
		{
			notOccurred.erase(a[i]);
		}

		cnt[a[i]]++;	
		cnt[a[i - m]]--;

		if (cnt[a[i - m]] == 0)
		{
			notOccurred[a[i - m]] = true;
		}

		ans = min(ans, notOccurred.begin()->first);
	}

	cout << ans << endl;
}