Baekjoon 5525번 IOIOI

문제

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

걸린 시간

- 실패

풀이

Python3

def getPi():
    pi = [0]*plen
    j = 0 # j : 비교대상 패턴(P) 인덱스
    for i in range(1, plen): # i : 비교할 패턴(P) 인덱스
        while j > 0 and P[i] != P[j]:
            j = pi[j-1]

        if P[i] == P[j]:
            j += 1
            pi[i] = j
    return pi

def kmp():
    ans = []
    pi = getPi()
    j = 0 # j : 패턴(P, pi) 인덱스
    for i in range(0, M): # i : 텍스트(S) 인덱스
        while j > 0 and S[i] != P[j]:
            j = pi[j-1]

        if S[i] == P[j]:
            if j == plen-1:
                ans.append(i-plen+1)
                j = pi[j]
            else:
                j += 1
    return ans    

if __name__ == "__main__":
    N = int(input()) # O의 개수
    M = int(input()) # 문자열 S의 길이
    S = list(input())

    P = []
    IO = ['I', 'O']
    for i in range(0, 2*N+1):
        P.append(IO[i%2])
    plen = len(P)

    print(len(kmp()))

주어진 문자열에서 특정 문자열(패턴)의 개수를 찾는 문자열 처리 문제이다. 각각의 길이를 M, N 라고 했을 때 패턴을 한 자리씩 옮겨가며 같은지 비교를 할 경우 복잡도는 O(NM) 으로 시간초과가 발생한다.

고지식한(무식한) 방법 대신 효율적인 검색 알고리즘을 사용해야 문제를 통과할 수 있다. 여러 알고리즘 중 KMP 알고리즘을 공부하여 문제를 해결했다.

KMP 알고리즘은 O(N+M) 으로 빠르게 문자열 검색을 할 수 있다. 잊지 말자는 취지에서 getPi 와 kmp 함수의 동작 과정을 애니메이션으로 나타내보았다.

참고

• KMP : 문자열 검색 알고리즘 - 멍멍멍