[백준 5525] IOIOI

🔗알고리즘 문제

로직 자체는 금방 작성했지만 예외처리를 하나 빼먹어서 오래걸린 문제 반례를 직접 생각하는 힘이 아직 부족하구나라는 것을 뼈져리게 느꼇다...

문제 분석

이 문제는 문자열 속에 P문자열이 몇 개 들어있는지 찾아내는 문제이다.

P문자열은 N+1개의 I와 N개의 O로 이루어져있는 문자열이다.

p = IOI
s = OOIOIOIO

OO [IOI] OIO
OOIO [IOI] O

발상 & 알고리즘 설계

처음에는 P문자열의 길이 만큼 탐색하여 문자열을 확인하는 Check라는 함수를 만들었다.

bool check(int idx, string &t, const string &s){
    if(idx < t.length() - 1)
        return false;

    string temp = "";

    for(int i = 0; i < t.length(); i++){
        temp.push_back(s[idx - i]);
    }

    return temp == t;
}

탐색의 갯수가 너무 많아져 시간초과가 발생하였다. 시간을 줄이기 위해서 P문자열이 시작되면 OI의 숫자를 세주는 방식으로 로직을 교체하였다.

for(int i = 0; i < m - 1; i++){
    if(isStart){
        if(s[i] == 'O' && s[i + 1] == 'I'){
            ++temp;
            ++i;
        }
        else{
            isStart = false;
            if(temp >= n){
                answer += temp - (n - 1);
            }
            temp = 0;
        }
    }

    if(!isStart && s[i] == 'I')
        isStart = true;
}

시간은 O(n)으로 줄일 수 있었지만 겹쳐있는 P문자열(IOIOI)를 판단할 수 없었다.

우리가 여기서 알아야 할 점은 P3문자열이 문자열 속에 있을 경우 P1 문자열이 3개 존재함을 보장한다는 점이다.

OO [IOIOIOI]

OO [IOI] OIOI
OOIO [IOI] OI
OOIOIO [IOI]

P3 문자열이 존재함 => P1 문자열은 3개 존재함

해당 방식을 사용해 겹친 문자열도 판단할 수 있게끔 로직을 수정하였다.

코드

#include <iostream>

using namespace std;

int main(){
    int n;
    int m;

    int answer = 0;
    int temp = 0;

    bool isStart = false;

    string s;

    cin >> n >> m >> s;

    for(int i = 0; i < m - 1; i++){
        if(isStart){
            if(s[i] == 'O' && s[i + 1] == 'I'){
                ++temp;
                ++i;
            }
            else{
                isStart = false;
                if(temp >= n){
                    answer += temp - (n - 1);
                }
                temp = 0;
            }
        }

        if(!isStart && s[i] == 'I')
            isStart = true;
    }

    if(isStart && temp >= n)
        answer += temp - (n - 1);

    cout << answer;
}