[백준] IOIOI

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

5525번: IOIOI

우선 문제부터 요약하면, 

 

I와 O로만 이루어진 문자열이 주어질 때, 해당 문자열에서 IOI가 반복되는 패턴을 반복수에 따라 P1, P2등으로 정의할 때, PN이 주어진 문자열에서 몇번 등장하는지 카운팅을 하는 문제입니다. 

 

<Solution>

일단 문자열의 길이가 100만개 까지 가능하기 때문에 O(N)이나 O(NlogN) 정도 까지의 복잡도만 사용이 가능합니다. 

 

그래서 IOI패턴이 등장하게 되면 IOI패턴이 총 몇번 반복되는 지를 통해 PN의 반복수를 결정하는 방식으로 시간 복잡도를 O(3*N)정도로 문제를 해결할 수 있습니다. 

 

간단하게 예시로 살펴보자면, 

 

N=2 인 상황에서 

IOIOIOI가 등장했다고 칩시다. 그러면 이 과정에서 IOI가 총 3번 반복되는 것을 알 수 있습니다. N=2 즉 IOIOI 패턴은 여기에 2번 등장합니다. IOIOIOI IOIOIOI

 

이렇게 2번 등장한다는 사실을 3-N+1을 통해 계산할 수 있습니다. (연속된 IOI의 갯수 - N + 1)

 

만약 이 값이 음수가 된다면 우리가 찾고자 하는 패턴보다 모자란 갯수의 연속된 IOI가 등장한 것이므로 음수가 아닌 0으로 처리해 주는 부분만 조심하면 됩니다. 

 

실제 구현은 아래와 같습니다.

#include <iostream>

using namespace std;

int N;
int M;
char S[1000000+10];

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

int solution(){
    int ret = 0;
    int consecutive = 0;
    for(int i = 0; i<M-2; i++){
        if(S[i] == 'I' && S[i+1] == 'O' && S[i+2] == 'I'){
            consecutive++;
            i++;
        }
        else{
            ret += (consecutive-N+1 >0) ? consecutive-N+1 : 0;
            consecutive = 0;
            continue;
        }
    }
    ret += (consecutive-N+1 >0) ? consecutive-N+1 : 0;

    return ret;
}

int main(){

    getinput();

    int ans = solution();

    cout << ans << endl;
    return 0;

}