[백준 5525] IOIOI

문제

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

5525번: IOIOI

 

 

문제 분석

우선 n과 m을 입력 받는다.

 

n은 IOI문자열의 크기이다. n이 1이라면 IOI, 3이라면 IOIOIOI이다. 

 

m은 확인할 문자열의 크기이다. 

 

받은 문자열에 n에서 입력 받은 크기의 문자가 몇개 있는지 세는 문제이다. 

 

 

알고리즘 설계

입력 받을 수 있는 것을 모두 입력 받는다. 

 

이후 for문을 돌려 0부터 m, 즉 입력 받은 문자열의 사이즈까지 돌아가는데 n의 입력 받은 크기와 앞에서 IOI관련 문자가 얼마나 있었는지 확인한 만큼까지만 돌려준다. 

 

i번쨰 문자가 I라면 시작 되는 것이기에 check변수를 만들어 1로, 

 

check가 0이 아니며 지금 문자와 바로 앞 문자가 OI면 check와 i을 모두 올리며 n보다 check가 더 크다면 입력 받은 n에 맞는 문자가 있는 것이기에 출력할 값을 1 올려준다. 

 

모두 아니라면 check를 0으로 한다. 

 

 

유의점

서브태스크가 존재하고, 시간 복잡도 관련이기에 for문 1개로 끝내는 것이 중요하다. 

 

굳이 체크하지 않아도 되는 곳을 체크할 수도 있기에 for문의 조건을 잘 설정해주어야 한다. 

 

 

코드 

#include <iostream>

using namespace std;

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

    int index, strSize, cnt = 0, check = 0;
    string str;
    cin >> index >> strSize >> str;

    for (int i = 0; i < strSize - (index * 2) + (check * 2); ++i)
    {
        if (str[i] == 'I')
            check = 1;
        else if (check != 0 && str[i] == 'O' && str[i + 1] == 'I')
        {
            ++check;
            ++i;
            if (check > index)
                ++cnt;
        }
        else
            check = 0;
    }

    cout << cnt;
}