[Problem Solving] BOJ 5525 : IOIOI

문제링크 : https://www.acmicpc.net/problem/5525

 

패턴을 선형적으로 찾으면 100점을 받을 수 없는 문제이다. 슬라이딩 윈도우의 방식으로 문제를 해결해야한다.

 

우선 cnt는 패턴에서 O의 개수이다.

1. S_0부터 S_M-2 까지 IO로 시작하는 부분이 있는지 찾는다. (S_i == I and S_i == O)

2. 그 시작하는 부분의 뒷부분이 IOI로 이어진다면(j = i + 1일 때, S_j = O and S_j+1 = I), cnt를 1 증가시키고, j를 2만큼 증가시킨다.

3. cnt가 N과 같다면, 즉 P_N과 일치하는 패턴이 하나 발견되었다면, and를 1증가시키고, 가장 찾은 지 오래 된 IO를 cnt에서 제외시키기 위해 cnt를 1감소시킨다.

4. 더이상 IOIOI의 형태로 이어지지 않는다면 cnt를 0으로 초기화하고, i를 j - 1로 변경한다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <algorithm>
#include <stack>
#include <set>
#include <cmath>
#include <climits>
#define endl '\n'
using namespace std;

int N, M;
string S;
int ans = 0;

void input()
{
    cin >> N;
    cin >> M;
    cin >> S;
}

void solution()
{
    int cnt = 0; // P_cnt
    for (int i = 0; i < M - 1; i++)
    {
        if (S[i] == 'I' && S[i + 1] == 'O') // IO로 시작되는 것을 찾았는데
        {
            int j = i + 1;
            while (j + 1 < M && S[j] == 'O' && S[j + 1] == 'I') // 그것이 IOI로 이어진다면
            {
                ++cnt;
                j += 2;

                if (cnt == N) // P_N을 찾았다면
                {
                    ++ans;
                    --cnt; // 가장 찾은 지 오래 된 IO는 cnt에서 제외
                }
            }
            cnt = 0;   // 더 이상 IOI...IOI 가 아니라면 cnt를 0으로 초기화하고,
            i = j - 1; // i를 j직전으로 변경
        }
    }
}

void output()
{
    cout << ans << endl;
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    input();
    solution();
    output();

    return 0;
}