[C++] 백준 5525번 IOIOI

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

풀이

Find, substr을 사용할 경우 시간초과로 50점만 받을 수 있다.

1. O(N)으로 해결하기 위해, "I"로 시작하는 지점을 찾고, 그 지점부터 "OI"가 나올 때마다 카운트 해준다.

2. 카운트가 N과 같아질 경우 원하는 문자열이므로 정답에 추가한다. 이때, k값을 -- 해줘야 한다.(찾은 문자열에서 가장 앞의 "IO"하나 빼주기로 생각)

3. i는 다음 OI를 찾아야 하므로 i+=2로 계속해서 탐색한다.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int N, M, res;
string org;
// N은 o의 개수, M은 str길이, I뒤에 OI가 N개 붙어있는게 몇개
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    // freopen("input.txt", "r", stdin);
    cin >> N;
    cin >> M;
    cin >> org;

    for (int i=0; i<M; i++){
        int k=0;
        if (org[i]=='O') continue;

        while (org[i+1]=='O' && org[i+2]=='I'){
            k++;

            if (k==N) {
                res++;
                k--;
            }
            i += 2;
        }
    }

    cout << res << endl;
    return 0;
}