백준 - IOIOI (5525)

5525번: IOIOI

 

이렇게 풀면 망한다.

이렇게 하면 시간초과가 발생한다.

I와 O만 이루어진 문자열에서 IOI패턴이 들어있는 패턴 문자열이 몇 번 일치하는 지 구하는 문제 입니다. 문자열 길이가 N이고, 패턴의 길이가 M(M은 3 이상의 홀수) 라고 할 때, 브루트 포스 방식으로 문자를 하나씩 순회할 때마다 일일히 패턴 길이를 순회해서 일치하는 지 검사를 하게 되면 O(N*M)의 시간이 걸리게 되므로 시간 초과가 발생합니다.

 

패턴의 정보를 활용

반복되는 부분은 검토를 할 필요가 없다.

패턴을 자세히 보면 IOIO...OI에서는 IOI가 반복되어 있습니다. 따라서 패턴이 일치하다는 것을 확인 한 후, 앞의 IO를 건너띄고 뒷부분 OI만 일치하는 지 여부만 판단하면 연속된 패턴을 찾을 수 있습니다. 반대로 일치하지가 않는다면, 다음 부분으로 한칸 넘겨서 검토하는 것이 아닌 틀린 위치에서 시작해서 일치 여부를 판단하면 됩니다. 이렇게 되면 문자열만 순회하게 되므로 O(N)의 시간이 걸리게 됩니다.

 

 

 

코드 보기

#include <iostream>
using namespace std;

int main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int N, M, l, r, ans;
    string s;
    
    cin >> N; cin >> M; cin >> s;
    l = r = 0; ans = 0;

    while(r < M) {
        if(l == r) {
            if(s.at(r) == 'I') r++;
            else l = ++r;
        } else {
            if((r - l) % 2 == 1) {
                // r에 O이 와야 한다
                if(s.at(r) == 'O') r++;
                else l = r;
            } else {
                // r에 I가 와야 한다
                if(s.at(r) == 'I') {
                    if((r-l)>>1 == N) {
                        ans++;
                        l += 2;
                    } else r++;
                } else l = r;
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

 

이렇게 일정하게 반복되는 문자열 정보를 활용해 좀 더 효율적으로 매칭 여부를 확인하는 이러한 아이디어는 단순히 I, O가 아닌 모든 문자로 확장을 시키면 KMP알고리즘으로 발전하게 됩니다. KMP알고리즘 역시 패턴의 정보를 활용한 문자열 매칭 알고리즘입니다. 이 문제도 KMP로 풀 수 있는 문제이며 KMP를 이해하는 데 초석이 되는 문제라고 생각합니다.

 

KMP로 푸는 문제 상당히 난해한 알고리즘이므로 KMP 알고리즘을 구글링 하신 후에 문제를 푸는 것을 권장합니다. 

1786번: 찾기