[BOJ] 5525. IOIOI

풀이

주어진 문자열에 어떤 패턴의 부분 문자열이 몇개나 존재하는지 구하는 문제이다. KMP 알고리즘에 대해 새롭게 공부했다. 

처음에는 완전 탐색으로 구현했다. 당연하게도 시간초과가 발생했다.

n = int(input()) m = int(input()) s = input() def check(s,n):     flag = True     for i in range(n-1):         if s[i]==s[i+1]:             flag = False             break     return flag   len_s = len(s) ans = 0 for i in range(len_s):     if s[i]=='I' and len_s-i>=n*2+1:         if check(s[i:i+(n*2)+1],n*2+1):             ans+=1 print(ans)

cs

완전 탐색을 했을 경우의 시간 복잡도는 O(n*m) 으로 굉장히 크게 나온다. 하지만 KMP 알고리즘을 사용하면 O(m)으로 문제를 해결할 수 있다.

KMP 알고리즘

패턴 문자열에 대해 prefix와 suffix를 비교해 jump 할 수 있는 문자열 길이를 저장해 탐색을 빠르게 하는 알고리즘이다. 다른 블로그 글을 읽었는데 아무리 읽어도 이해가 안돼서 동빈나님의 유튜브 강의를 참고했다. 아직도 100% 이해는 되지 않는다.ㅠㅠ

n = int(input()) m = int(input()) s = input()   def get_pi_table(m, s):     pi = [0]*m     j = 0     for i in range(1,m):         while j>0 and s[j]!=s[i]:             j = pi[j-1]         if s[j]==s[i]:             pi[i] = j+1             j+=1     return pi   def KMP(s, m, pattern, pi):     pattern_size = len(pattern)-1     j = 0     ans = 0     for i in range(m):         while j>0 and s[i]!=pattern[j]:             j = pi[j-1]         if s[i] == pattern[j]:             if j == pattern_size:                 ans+=1                 j = pi[j]             else:                 j+=1     return ans          pattern = 'I'+'OI'*n pi = get_pi_table(2*n+1,pattern) print(KMP(s,m,pattern,pi))

cs