오늘의 알고리즘 boj-16172

문제

친구가 적은 성민이는 수업에 결석해도 시험이나 과제에 대한 정보를 제대로 얻을 수 없었다. F 학점을 받을 위기까지 아슬아슬하게 결석일 수를 유지하던 성민이는, 어느 날 갑자기 영문도 모른 채 쪽지시험을 보게 되었다!

갑작스러운 쪽지 시험으로 마음이 급해진 성민이는 매직아이를 사용해 벼락치기를 하기로 한다.

성민이가 듣는 과목의 교과서는, 알파벳 소문자(a-z)와 알파벳 대문자(A-Z)로만 이루어져 있다. 성민이가 교과서에서 찾고자 하는 키워드도 역시 알파벳 소문자와 대문자로만 이루어져 있다. 하지만, 성민이에겐 큰 문제가 생겼다. 결석한 날의 수업 내용을 친구에게 빌려 필기를 하던 중, 교과서에 숫자(0-9)를 적어버린 것이다.

키워드를 찾기 힘들어 패닉에 빠진 성민이는 몇 안 되는 친구인 당신에게 도움을 요청했다. 성민이를 도와, 교과서에서 성민이가 찾고자 하는 키워드의 존재 여부를 알려주자.

풀이

사실 이 문제는 python으로 엄청 간단하게 풀 수 있는 문제다. 정규표현식으로 문자열만 추출한 다음 in으로 검증해주고 검증된 여부를 인트로 변환해 프린트 해주면 된다.

import re

origin_word = re.sub('[0-9]', "", input())
check_word = input()

print(int(check_word in origin_word))

그러나 kmp 예제(바킹독님)이므로 kmp로 접근해보자.

kmp를 통해서 풀이 하되 숫자 부분만 무시해주면 풀 수 있는 문제다.

실패함수를 통해 실패테이블을 만들고 실패테이블을 참고하여 서브스트링값인지 확인해준다.

kmp는 알고리즘 자체보다 실패함수, 테이블처럼 새로운 개념을 찾아낸 아이디어에서 영감을 많이 받으면 좋을 것 같다.

알고리즘의 반복숙달도 물론 중요하다.

def get_failure_table(check_word):
    length = len(check_word)
    failure_table = [0] * length
    
    j = 0
    for i in range(1, length):
        while j > 0 and check_word[i] != check_word[j]:
            j = failure_table[j-1]
        if check_word[i] == check_word[j]:
            j+=1
            failure_table[i] = j
    return failure_table


def is_sub_string(origin_word, check_word):
    j = 0
    for i in range(len(origin_word)):
        if "0"<= origin_word[i] <= "9":
            continue
        while j > 0 and origin_word[i] != check_word[j]:
            j = failure_table[j-1]
        if origin_word[i] == check_word[j]:
            j+=1
        if j == len(check_word): return True
    return False

origin_word = input()
check_word = input()


failure_table = get_failure_table(check_word)

print(int(is_sub_string(origin_word, check_word)))