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

문제 링크

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

🕒 Python 풀이시간: 50분

def create_PSL(pattern):
    i=0
    table=[0 for _ in range(len(pattern))]
    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

s=input()
answer=0
for i in range(len(s)):
    answer=max(answer,max(create_PSL(s[i:])))
print(answer)

문자열 반복 최대 길이 찾기! 🔍✨

문자열에서 두 번 이상 반복되는 문자열의 최대 길이를 구하는 것이기 때문에 두 번 이상을 어떻게 확인하나 고민했었다. kmp 알고리즘을 통한 반복문을 생각은 했었으나 0.5초가 문제의 조건으로 주어졌기 때문에 가능할까 고민하다가 시간을 많이 소요하였다.

풀이 방법은 kmp 알고리즘만 알고 있다면 간단하다. PSL을 구하는 과정에서 우리는 이미 두번 반복되는 최대 길이를, 즉 접두사와 접미사를 구하기 때문에 이를 모든 문자열의 시작점과 끝점에 대해 반복하면 되는데 PSL table을 구하는 것 자체에서 이미 끝지점은 갱신하기 때문에 시작지점만 바꿔주면서 최댓값을 구해주면 된다. 그렇게 모든 시작점에 대해서 각 문자열의 PSL을 구해서 그 중 최댓값을 구한다면 정답이 된다.

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