JOI20 JJOOII 2

문제

https://oj.uz/problem/view/JOI20_ho_t2

문제 보기 - JJOOII 2 (JOI20_ho_t2) :: oj.uz

길이 $N$의 문자열과 $K$가 주어졌을 때 J, O, I의 연속한 $K$개의 문자로 이루어진 JJJJJOOOOOIIIIII와 같은 문자열을 만들어야 한다. 할 수 있는 연산은 (1) 왼쪽, 오른쪽에서 문자 제거 / (2) 중간에 있는 문자 제거 의 2가지 연산일 때 2번 연산의 수를 최소화해야 한다.

$N<=200000$

 

풀이

다양한 풀이가 가능하다.

 

JJJJJOOOOOIIIII를 포함하는 가장 작은 부분문자열을 찾으면 된다.

각 위치를 끝점으로 생각하고 I, O, J에 대해 pos보다 작은 위치이며 지금까지 등장한 문자들 중 이분탐색을 이용하여 오른쪽에서 $K$번째 문자를 찾으면 된다.

 

다른 풀이로는, $A_i=$$1$~$i$까지 중 오른쪽에서 $K$번째 J의 위치, $B_i=$$i$~$N$까지 중 왼쪽에서 $K$번째 I의 위치를 전처리한 후, 가장 오른쪽 O의 위치를 고정하고 오른쪽에서 K번째 O에 대해 잡을 수 있는 최소 크기의 구간을 계산하면 된다.

 

시간 복잡도 : $O(NlogN)$, $O(N)$

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 2e5;
 
int N, K;
char S[MAXN+10];
int P[MAXN+10], Q[MAXN+10];
 
int main()
{
	scanf("%d%d", &N, &K);
	scanf("%s", S+1);
 
	vector<int> V;
	P[0]=-1;
	for(int i=1; i<=N; i++)
	{
		if(S[i]=='J') V.push_back(i);
		if(V.size()<K) P[i]=-1;
		else P[i]=V[V.size()-K];
	}
	V.clear();
 
	Q[N+1]=-1;
	for(int i=N; i>=1; i--)
	{
		if(S[i]=='I') V.push_back(i);
		if(V.size()<K) Q[i]=-1;
		else Q[i]=V[V.size()-K];
	}
	V.clear();
 
	int ans=2e9;
	for(int i=1; i<=N; i++)
	{
		if(S[i]=='O') V.push_back(i);
		if(V.size()<K) continue;
		else
		{
			int p=V[V.size()-K], q=i;
			int l=P[p-1], r=Q[q+1];
			if(l==-1 || r==-1) continue;
			ans=min(ans, r-l+1);
		}
	}
 
	if(ans==2e9) return !printf("-1\n");
	printf("%d\n", ans-3*K);
}