앳코더90 - 034 - There are few types of elements（★4 )

 

https://atcoder.jp/contests/typical90/tasks/typical90_ah

034 - There are few types of elements（★4）

 

N개의 원소가 주어질때 포함된 요소가 K개 이하인 연속된 부분수열의 길이를 구하라.

7 2

1 1 2 2 3 3 4 

로 주어지면 2개이하인 연속된 부분수열로 1,1,2,2 / 2,2,3,3 으로 최대길이는 4다. N의 최대가 10만개이므로 모든 경우의수를 계산하는 N^2의 방법으로는 불가능하다.

 

이를 O(N)만에 계산하는 신기한 방법이 있다. 바로 투포인터를 이용한 방법이다. 다음 원소를 map에 넣으면서 map의 크기가 K이하를 유지하며 진행하는 것이다. 다음 원소를 넣으면 K를 넘칠것 같을때 가는것을 멈추고 Left를 끌어오는 방식이다. 

 

이를 코드로 구현하면 아래와 같다.

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_set>
#include <numeric>
#include <random>
#include <iostream>
#include <unordered_map>
#include <atcoder/all>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back

using namespace std;
using namespace atcoder;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<long long> vll;

const int INF = 2000000000;
const double pi = 3.14159265358979;
const int MOD = 100000;

void yesno(bool a)
{
	if (a)
		cout << "YES\n";
	else
		cout << "NO\n";
}

vi v;
int N, K;
int ans;

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

	cin >> N >> K;

	v.resize(N);

	rep(i, N) 
	{
		cin >> v[i];
	}

	map<int, int> m;
	int l = 0;
	int r = 0;

	while (l <= r && r < N)
	{
		if (m.size() == K && m.find(v[r]) == m.end())
		{
			m[v[l]]--;
			if (m[v[l]] == 0)
				m.erase(v[l]);
			l++;
		}
		else
		{
			m[v[r]]++;
			r++;
		}
		ans = max(ans, r - l);
	}

	cout << ans;

	return 0;
}

 

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

나는 예전에 이 문제에서 비슷한 풀이로 해결했기 때문에 쉽게 생각해 낼 수 있었다.