[백준/BOJ] 5525 IOIOI

문제 : 5525 IOIOI

5525번: IOIOI

x가 주어졌을 때, x+1개의 I와 x개의 O가 교대하는 문자열의 개수를 찾아 출력하는 문제이다.

그냥 중첩 반복문을 사용해 풀게 되면 O(N^2)으로 시간 초과가 나게 되므로

시간을 O(N)으로 줄여야 한다.

가장 길게 교대하는 문자열의 크기가 y이라고 할 때,

안에 속하는 부분 문자열의 개수는 y-x+1 임을 활용하여 풀면 된다.

---

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll N, M, ans=0;
    string S;
    cin >> N >> M >> S;
    for (int i=0;i<M;i++){
        if (S[i]=='I'){
            ll cnt=0;
            while (S[i+1]=='O' && S[i+2]=='I'){
                cnt++;
                i+=2;
            }
            if (cnt>=N)
                ans+=cnt-N+1;
        }
    }
    cout << ans;
    return 0;
}