[Algorithm] Baekjoon 5525번 : IOIOI

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

5525번: IOIOI

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
    int m = 0;
    string input = "";
    int answerCount = 0;
 
    cin >> n >> m >> input;
 
    for (int i = 0; i < m; i++)
    {
        if (input[i] == 'O') continue;
        int tCount = 0;
 
        while (i+2 < m)
        {
            if (input[i + 1] == 'O' && input[i + 2] == 'I')
            {
                tCount++;
                i += 2;
                if (tCount >= n) answerCount++; // 기준문자열 충족이후, 추가 카운팅.
            }
            else break;
        }
    }
 
    cout << answerCount;
}

 

처음 접근은 아주 당연?하게도 substr로 구간별 체크해서 풀이 -> 50점만 받았다.

이 문제는 조건에 따라 점수를 주는데, 시간제한 1초 기준하에 N이 100이하 M이 100만이하면 substr로 풀어도 풀리긴 한다. 

다만 N도 100만이하일 경우엔 시간초과가 뜬다. 

당연하게도 다른 풀이로 해결하라는 의도이다.

 

문제에서 규칙을 찾자면, N이 1이라고 가정해보자. 그러면 IOI 이다.

그리고 M이 "IOIOIOIOI" 라고 주어졌을 때, 어떠한 규칙이 있다.

 

I 이후에 'O와 I'가 몇번 나오느냐에 따라 값을 결정할 수 있다...!

 

N이 1일때 IOI 인데, 만약 M에서 어떤 구간에서 I 이후에 O와 I가 연속으로 1번 나왔다고 가정하면, 일단 1개는 찾은것이다.

근데 또 O와 I가 연속으로 나온다면 2개를 찾은것이다. IOIOI 이면, IOI가 두개 들어있는거니까.

이런식으로 I 이후에 O와 I가 연속으로 나오는 횟수(tCount)를 카운팅하고, 그 카운팅값이 N번 나왔다고 가정하면, 

일단 그 문자열구간은 기준문자열(N에 따른 문자열)을 만족하게 된다.

만족한 순간, 이후에도 O와 I가 연속으로 나온다면, 문자열규칙상 최종카운트도 +1씩 증가하게된다.

 

예시 :

기준문자열 : N == 2 ->   IOIOI 

비교문자열 : OOIOIOIOIIOII

 

OOIOIOIOIIOII   // 인덱스 2에 위치한 파란색 I기준으로 잡고, 이후 O와 I가 연속으로나오는 횟수 체크. 

                           // 일단 2번은 연속된걸(빨간색부분) 알았으니, 기준문자열(N==2)과 같다는걸 알 수 있다. 

                           // 그렇기 때문에 최종카운팅도 +1

 

OOIOIOIOIIOII   //  이후 추가적으로 체크하면서 한번 더 O와 I가 반복된걸 알았다.(노란색부분)

                           // 이미 기준문자열을 충족한 상태에서 추가적으로 반복됐으니, 바로 최종카운팅을 한다.