[C++] BaekJoon 5525 IOIOI

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

---

이 문제는 Pn이 몇 군데 포함 되어 있는지 구하는 문제이다. 

Pn은 N+1개의 I와 N개의 O로 이루어져 있다.

마지막에 무조건 I가 나온다는 점을 이용하여 문자열로 코드를 구현하였다. 

 

코드

#include <iostream>
#include <string>

using namespace std;

int N, M;

int main() {
    string S;
    // 입력 받기 OOIOIOIOIIOII(13)
    cin >> N; //Pn
    cin >> M; //입력 글자 수, 반복문에 사용한다 
    cin >> S; //입력

    int count = 0; //몇 군데 포함되어있는지 카운트 
    for (int i = 0; i < M; i++)
    {
        //length, N의 길이
        int length = 0;

        //시작 문자가 'O'일 경우, 반복문을 실행하지 않고 다음으로 넘어간다.
        //주어진 문자열은 무조건 I로 시작하기 때문
        if (S[i] == 'O')
        {
            continue;
        }
        else
        {
            while (S[i + 1] == 'O' && S[i + 2] == 'I')
            {
                //length에 1을 더한다.
                //예를 들면, N = 2은 IOIOI이다, 이는 S[i]이 I, S[i+1]이 O, S[i+2]가 I일 때
                //이를 하나로 보고 length에 1을 더한다. if문에 적합하지 않으면 한번 더 반복하여 OI를 카운트 해
                //length에 1을 또 더해 length는 2가 된다.
                length++;
                //N = 2이므로, 카운트를 추가한다.
                //length--를 하는 이유는 이미 발견한 패턴에 대해 중복 계산을 방지하기 위한 것.
                if (length == N)
                {
                    count++;
                    length--;
                }
                //i에 2를 더해 N의 길이만큼 늘려서 탐색한다. 
                i += 2;
            }
        }
        length = 0;
    }
    cout << count;

    return 0;
}

설명

주어진 문자열에서 특정 패턴의 반복을 찾고 해당 패턴이 몇 번 등장하는지를 세는 작업을 한다. 

 

반복문은 문자열의 길이(M) 만큼 실행된다.

이때 시작하는 문자가 O일 경우 패턴을 찾는 것이 아니므로 넘어간다.

I로 시작하는 경우, 패턴을 찾아내기 시작, 이때 OI 패턴을 찾으면 length를 1 증가시킨다. 

 

이후, length = N 일 경우 즉, 원하는 패턴의 길이와 같아진다면, 해당 패턴이 발견되었다고 판단하고 count 증가

length를 감소시킴으로써 중복 계산을 방지한다. 후에 length를 초기화하여 다음 패턴을 탐색한다.