문자열이 하나 주어졌을 때, 그 문자열이 동일한 부분 문자열이 여러 번 이어진 '반복 문자열'인지 확인해야 하는 경우가 있습니다.
예를 들어 입력이 "helloworldhelloworld"라면, "helloworld"가 두 번 반복된 형태이므로 결과는 True가 됩니다.
알고리즘
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- 문자열의 길이를 n에 저장합니다.
- n의 모든 약수를 구하는 findFactors() 함수를 정의합니다.
- 빈 집합(set) f를 만들고, 탐색용 변수 i를 1로 초기화합니다.
- i × i ≤ n인 동안 다음을 반복합니다.
- n을 i로 나눈 나머지가 0이라면, 몫(n / i)과 i를 집합 f에 추가합니다.
- i를 1 증가시킵니다.
- f를 반환합니다.
- 메인 로직에서는 다음과 같이 진행합니다.
- fact := findFactors(n)
- fact의 각 약수 i에 대해 다음을 수행합니다.
- i가 n과 같다면 건너뜁니다. (문자열 전체 자신은 반복 단위에서 제외)
- ss := 문자열의 처음 i글자로 이루어진 부분 문자열
- val := 전체 문자열 안에서 ss가 등장한 횟수
- val이 n / i와 같다면 True를 반환합니다.
- 모든 약수를 확인했는데도 조건을 만족하지 않으면 False를 반환합니다.
예제 코드
class Solution:
def solve(self, s):
n = len(s)
def findFactors(n):
f = set()
i = 1
while i * i <= n:
if n % i == 0:
f.add(int(n / i))
f.add(i)
i += 1
return f
fact = findFactors(n)
for i in fact:
if i == n:
continue
ss = s[:i]
val = s.count(ss)
if val == int(n / i):
return True
return False
ob = Solution()
print(ob.solve("helloworldhelloworld"))입력
"helloworldhelloworld"
출력
True
동작 원리
핵심 아이디어는 간단합니다. 문자열이 어떤 부분 문자열의 반복으로 이루어져 있다면, 반복 단위의 길이는 반드시 전체 길이 n의 약수여야 합니다. 따라서 n의 약수만 후보로 삼고, 각 후보 길이 i마다 앞부분 i글자를 잘라낸 뒤 그것이 문자열 전체에서 정확히 n / i번 등장하는지 검사하면 됩니다.
예제의 "helloworldhelloworld"는 길이가 20이며, 약수인 10을 반복 단위로 삼으면 "helloworld"가 정확히 2번 등장하므로 반복 문자열임을 알 수 있습니다.
참고로 파이썬에서는 문자열을 두 배로 늘린 뒤 위치를 확인하는 (s + s).find(s, 1) != len(s) 같은 우아한 한 줄 트릭으로도 같은 문제를 해결할 수 있으니, 상황에 맞게 활용해 보시기 바랍니다.