[Python] 4354번 문자열 제곱

 

 

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

---

 

24/09/26

 

 

KMP로 유명한 문제다. 근데 이 문제는 KMP로 안풀어도 된다. 사실 이 방법이 더 쉽다.

---

 

문제 접근 방식:

 

 

엥 그러면 어떻게 접근하는 거야, 라고 생각하겠지만, 그냥 나이브하게 풀린다.

 

문자열의 길이를 $N$이라고 하면, $N$의 약수가 반복되는 문자열의 길이가 될 수 있다.

 

따라서 $N$의 약수 $i$에 대해서, 기존 문자열 $S$를 슬라이싱한 부분 문자열, $S[:i]$가 $S$에서 몇 번 반복되는지 count함수를 통해 확인한다.

 

그 반복 횟수*부분문자열의 길이가 원래 문자열의 길이 $N$이 된다면 바로 종료하면 된다.(가장 짧은 부분 문자열을 찾는 것이므로)

 

그렇다면 이게 왜 되는지 궁금할텐데, 파이썬에서 str.count()는 $\mathcal{O}(n)$의 시간복잡도를 가지고 있다.

 

따라서 그냥 돌면 충분히 돌아간다!!

 

개인적으로 문제 난이도가 더 하향되어야 한다고 생각함...

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 4354번 문자열 제곱
'''
접근 방법:
나이브 풀이
'''
import sys
input = sys.stdin.readline

while True:
    S = input().rstrip()
    if S == '.':
        break
    N = len(S)
    for i in range(1,N+1):
        if N % i == 0:
            k = S.count(S[:i])
            if k*i == N:
                print(k)
                break