[코딩테스트][백준] 🔥 백준 4354번 "문자열 제곱" 문제: Python과 Java으로 완벽 해결하기! 🔥

문제 링크

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

🛠️ 미해결

• 풀이시간 : 1시간 이상
• 틀린 이유 : PSL을 구하는 과정에서 가장 긴 공통된 접두사와 접미사를 제외한 문자열이 해당 문자열의 가장 긴 패턴이 된다는 사실을 모르고 있었다. 해당 내용은 따로 빼서 강의를 듣고 정리해 두었다.
  https://velog.io/@ouk/%EB%AC%B8%EC%9E%90%EC%97%B4-%EA%B2%80%EC%83%89%EC%9D%98-%ED%98%81%EB%AA%85-KMP-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%99%84%EC%A0%84-%EC%A0%95%EB%B3%B5

🕒 Python 풀이시간: x

def create_pi_table(pattern):
    table = [0] * 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

while True:
    s = input().strip()
    if s == '.':
        break
    table = create_pi_table(s)
    n = len(s)
    # 주기 계산
    period = n - table[n - 1]
    if n % period == 0:
        print(n // period)
    else:
        print(1)

문자열의 반복되는 최소 패턴은 즉, 주기는 가장 긴 접두사나 접미사를 제외할 때 이므로 이를 화룡해서 주기의 길이를 구하고 이 주기가 반복될 수 있는지를 나머지 연산을 통해 구해주면 된다. 만약 나누어 떨어진다면 완전히 반복되므로 이를 나누어 출력하면 되고 그렇지 않을 경우에는 반복이 불가능 하므로 전체가 한 패턴 취급이 되어 1을 출력하면 된다.

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