[Python][백준] 문자열 탐색 알고리즘 공부하기 | 백준 5525번 50점

import sys


def P5525():
    n = int(input())
    pn = 'I' + 'OI' * n
    length = int(input())
    string = input().strip()

    sum, x = 0, 0
    while x < length:
        if pn in string[x:]:
            x += 1
            sum += 1
        x += 1

    print(sum)


if __name__ == '__main__':
    input = sys.stdin.readline
    P5525()

내가 푼 문제이다. 50점 나왔다. 왜 50점 나왔나 했더니

시간 복잡도 문제란다.

 

3학년 때 피똥싸며 들은 알고리즘 강의에 나온 문자열 탐색 알고리즘을 사용할 때인가...!

 

문자열 탐색 알고리즘은 여러가지가 있다.

내가 짠 코드는 순차탐색이다. O(n)의 시간복잡도를 가진다?

 

그 외에는 KMP, Rabin-Karp가 있다.

막 앞으로 갔다가 뒤로 갔다가 얼마만큼 뛰어넘어갔다가 했던거 같은데...

기억이 가물가물가물치

Abdul Bari 교수님 강의를 보고 배우자

https://youtu.be/V5-7GzOfADQ

KMP Algorithm

 

 

https://youtu.be/qQ8vS2btsxI

Rabin-Karp Algorithm

다음 포스트는 String matching Algorithm을 완벽히 공부하고 오겠다.