[코딩테스트][백준] 🔥 백준 7575번 "바이러스" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

https://www.acmicpc.net/problem/7575

🕒 Python 풀이시간: 40분

def create_pi_table(pattern):
    table=[0 for _ in range(len(pattern))]
    i=0
    for j in range(1,len(pattern)):
        while i>0 and pattern[i]!=pattern[j]:
            i=table[i-1]
        if pattern[i]==pattern[j]:
            i+=1
            table[j]=i
    return table

def kmp(all_string,pattern):
    table=create_pi_table(pattern)

    i=0
    result=[]
    for j in range(len(all_string)):
        while i>0 and pattern[i]!=all_string[j]:
            i=table[i-1]
        if pattern[i]==all_string[j]:
            i+=1
            if i==len(pattern):
                result.append(j-i+2)
                i=table[i-1]
    return result

N,K=map(int,input().split())
programs=[]
programsToString=[]
for _ in range(N):
    mL=int(input())
    program=list(map(int,input().split()))
    programs.append(program)
    programsToString.append(" ".join(map(str,program)))

result=False
for i in range(0,len(programs[0])-K+1):
    pattern=programs[0][i:i+K]
    reversePattern=pattern[::-1]
    thisPatternIncluded=True
    for j in range(1,len(programs)):
        if len(kmp(programsToString[j]," ".join(map(str,pattern))))>0 or len(kmp(programsToString[j]," ".join(map(str,reversePattern)))):
            continue
        else:
            thisPatternIncluded=False
            break
    if thisPatternIncluded:
        result=True
        break
if result:
    print("YES")
else:
    print("NO")

🦠 문자열 속 바이러스를 찾아라! KMP로 패턴 탐색 최적화하기 🚀

바이러스라는 코드를 찾아내는 문자열 관련 문제이다. 이 때, 문자열이 정수형으로 주어져있기 때문에 이를 어떻게 처리하나 순간적인 고민이 잠깐 들었지만 단순히 python의 join을 통해 연결을 통해 문자열 탐색으로 즉, KMP를 통해 존재 여부를 빠르게 확인할 수 있었다.

이러한 생각을 했다면 시간복잡도를 고려해보면 된다. 모든 문자열에 K 길이의 문자열 패턴이 존재해야 하므로 한 문자열만 관련해서 패턴을 추출하면 되므로 일단 최대 1,000의 연산이 나온다. 그 후 모든 문자열에서 해당 패턴을 확인해야 하므로 문자열의 최대 수인 x100을 해준다고 생각할 수 있다. 이제 마지막으로 각 문자열마다 KMP로 탐색을 한다면 $O(N+M)$인 즉 1,100회의 연산을 해야하므로 대략 1억 정도가 나와 연산횟수에서는 아슬아슬하게 가능하다고 볼 수 있다.

다음의 설계를 바탕으로 코드를 작성해주면 된다. KMP 알고리즘을 작성하고 각 패턴을 추출하는 대신 거꾸로 뒤집어진 패턴도 가능하므로 이 패턴또한 만들어놓는다. 그리고 둘 중 하나가 각 패턴에 존재하면 바로 가지치기 식으로 종료시키면 된다.

이렇게 Python으로 백준의 "바이러스" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊