[알고리즘] BOJ 5525 IOIOI - Fri, Nov 6, 2020

제목은 이상하지만 재미있는 문제

KMP를 이용한 문자열 패턴 매칭

https://www.acmicpc.net/problem/5525 문제는 상당히 재미있는 문제였다.

Try 1

언뜻 보면 단순 문자열 비교를 통해서 풀 수 있을 것 같은 문제라 그렇게 풀어 보았다.

생각해 보면 복잡도가 O(n * m) 이기 때문에 당연히 TE (시간초과) 가 발생한다.

using namespace std;

string pstr(int n) {
    string o = "IO";
    string ans = "";
    for (int i = 0; i < n; i++) {
        ans += o;
    }
    return ans + "I";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, l;
    int ans = 0;
    string s;
    cin >> n >> l;
    cin >> s;
    int psize = 2 * n + 1;
    string pn = pstr(n);
    
    for (int i = 0; i < s.size() - psize; i++) {
        if (s.substr(i, psize) == pn) ans++;        
    }

    cout << ans << "\n";
    return 0;
}

Try 2

결국 문자열 비교의 정석 KMP를 변형해서 적용했다. 비교대상 문자열이 일정하기 때문에 원래의 KMP보다 구현이 쉽다. KMP는 종만북 20장 즈음에도 나왔던 것 같은데, 문자열 문제가 종종 코딩 테스트에도 나오므로 숙지하면 좋을 것 같다. 개인적으로 KMP 알고리즘은 어렵지 않은데 실패함수를 효율적으로 구현하는 게 더 어려운 느낌이다.

KMP 참고링크

using namespace std;

int match(string &s, int pos, int n, int jmp) {       
    int i = jmp; 
    for (;i < 2 * n + 1; i++) {
        if (i % 2 == 0 && s[pos + i] != 'I') return i;
        if (i % 2 == 1 && s[pos + i] != 'O') return i;        
    }
    return i;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;

    int i = 0;
    int ans = 0;
    int jmp = 0;

    while(i < s.size() - 2 * n + 1) {
        int w = match(s, i, n, jmp);
        if (w == 2 * n + 1) {
            ans++;
            i+= 2;
            jmp = 2 * n - 1;
        } else if (w == 0) {
            i++;
            jmp = 0;            
        } else {
            i+= w;
            jmp = 0;
        }        
    }

    cout << ans << "\n";
    return 0;
}

Try 3

페이스북 매일코딩 그룹에서 H님과 J님의 코드를 보니 더 간단히 풀 수 있다는 것을 알았다.

• H님 소스
• J님 소스

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    
    int ans = 0;

    for(int i = 0; i < s.size() - (2 * n  + 1); i++) {
        if (s[i] == 'I') {
            int p = 0;
            while (s[i + 1] == 'O' && s[i + 2] == 'I') {
                p++;
                i+=2;
            }
            if (p >= n) {
                ans += p - n + 1;             
            }
        }
    }
    
    cout << ans << "\n";
    return 0;
}

재밌는 문제를 풀어서 풀이를 정리해 봤다.

오늘도 즐거운 코딩 라이프!