IOIOI C++ - 백준 5525

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

이 문제는 문자열의 길이 범위가 10^6이라서 문자열 간 비교하는

알고리즘으로는 시간 초과가 났다.

따라서 다른 방법으로 접근해야했다.

다음의 알고리즘은 $O(N)$으로 설계했다. 과정은 다음과 같다.

바로 전에 있던 부분 문자열이 O면 I를, I면 O를 감지하는 if문을
작성해 개수를 하나씩 늘려주었고, 만약 $2*N+1$를 만족하면
ans를 하나씩 늘려주었다.

만약 O,I가 연속으로 나와 IOI...이 불가능한 경우도 처리해주었다.

코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

string S;
int n,m,cnt=0,ans=0;
bool ioturn=false; //true i turn
                   //false o turn
int main(){
	cin >> n >> m >> S;
	for(int i=1;i<=m;i++){
		if(ioturn){
			if(S[i-1]=='O'){
				ioturn=false;
				cnt++;
			}
			else cnt=1;
		}
		else{
			if(S[i-1]=='I'){
				ioturn=true;
				cnt++;
			}
			else{
				cnt=0;
			}
		}
		if(cnt==2*n+1){
			ans++;
			cnt=2*n-1;
		}
	}
	cout << ans;
}