1. 문제 설명

나는 친구가 적다

2. 문제 분석

원본 문자열을 가공한 새로운 문자열(숫자가 없는 버전)을 만들 때 처음에는 for문으로 letter.isdigit() 혹은 letter.isalpha()로 확인했는데, 시간 초과가 났다. 이후 리스트 컴프리헨션 방식으로 변경 이후 KMP 알고리즘을 사용하니 시간 안에 통과되었다. 리스트 컴프리헨션을 잘 사용하자.

3. 나의 풀이

import sys

s = sys.stdin.readline().rstrip()
k = sys.stdin.readline().rstrip()

def KMP(source, target):
    result = []
    source_len = len(source)
    target_len = len(target)

    LPS = [0 for _ in range(target_len)]

    LPS_compute(target, LPS)

    source_idx, target_idx = 0, 0

    while source_idx < source_len:
        if target[target_idx] == source[source_idx]:
            source_idx += 1
            target_idx += 1
        else:
            if target_idx == 0:
                source_idx += 1
            else:
                target_idx = LPS[target_idx-1]

        if target_idx == target_len:
            return True
    return False

def LPS_compute(target, LPS):
    length = 0
    idx = 1
    while idx < len(target):
        if target[idx] == target[length]:
            length += 1
            LPS[idx] = length
            idx += 1
        else:
            if length == 0:
                LPS[idx] = 0
                idx += 1
            else:
                length = LPS[length-1]

new_s = [letter for letter in s if letter.isalpha()]
new_s = "".join(new_s)


if KMP(new_s, k): print(1)
else: print(0)