백준 1786번: 찾기 (Python)

접근

접근 방법은 문제에 주어져 있다. 주어진 방법대로 문제를 풀었는데 혼자서는 40% 시간초과를 넘기기가 힘들어 KMP 알고리즘에 대해 공부도 하고, 다른 분들의 코드를 참고하여 풀 수 있었다.

KMP 알고리즘 개념: KMP 알고리즘 개념

커누스-모리스-프랫 알고리즘 - 위키백과, 우리 모두의 백과사전

코드

import sys


def kmptable(p):
    n = len(p)
    table = [0] * n
    j = 0
    for i in range(1, n):
        while j > 0 and p[i] != p[j]:
            j = table[j - 1]
        if p[i] == p[j]:
            j += 1
            table[i] = j
    return table


def kmp(s, p):
    j = 0
    cnt = 0
    pos = []
    for i in range(len(s)):
        while j > 0 and s[i] != p[j]:
            j = table[j - 1]
        if s[i] == p[j]:
            j += 1
            if j == len(p):
                cnt += 1
                pos.append(i - len(p) + 2)
                j = table[j - 1]
    return cnt, pos


s = sys.stdin.readline().rstrip()
p = sys.stdin.readline().rstrip()
table = kmptable(p)

cnt, pos = kmp(s, p)
print(cnt)
print(*pos)

더 생각해 볼 것?

내가 고안한 코드가 어떤점이 부족하여 계속 시간 초과가 뜨는지 완성 코드를 기반으로 공부해보아야 겠다.

40%까지 진행된 것을 보면 코드가 틀린 것은 아닌데, 비효율이 발생하는 부분을 찾아보는 것이 좋을 것 같다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!