[백준/BOJ] 4353. 문자열 제곱

문제 링크 : www.acmicpc.net/problem/4354

4354번: 문자열 제곱

문제

알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다.

이러한 이어 붙이는 것을 곱셈으로 생각한다면, 음이 아닌 정수의 제곱도 정의할 수 있다.

• a^0 = "" (빈 문자열)
• a^(n+1) = a*(a^n)

문자열 s가 주어졌을 때, 어떤 문자열 a에 대해서 s=a^n을 만족하는 가장 큰 n을 찾는 프로그램을 작성하시오.

입력

입력은 10개 이하의 테스트 케이스로 이루어져 있다. 각각의 테스트 케이스는 s를 포함한 한 줄로 이루어져 있다. s의 길이는 적어도 1이며, 백만글자를 넘지 않는다. 마지막 테스트 케이스의 다음 줄은 마침표이다.

출력

각각의 테스트 케이스에 대해, s=a^n을 만족하는 가장 큰 n을 찾은 뒤 출력한다.

---

풀이 과정

의외로 직접 풀었을 때는 별거 아닌 문제입니다.

n이 올 수 있는 수는 문자열의 길이의 약수입니다. 문자열 길이를 조금 보고있을 수록 더 높은 n이 나오기 때문에 작은 수가 나오면 break를 해주고 결과값을 출력해주면 됩니다.

문자열 길이의 약수이면 문자열을 잘라서 문자열 제곱이 성립하는지를 확인하면 되는 문제입니다.

중간에 입력을 끝까지 받기 위해 sys.stdin.read()를 사용해주었습니다. .을 만나면 EOF이니 그냥 끝내주면 됩니다.

import sys

def solution(data):
  res = 1

  for i in range(len(data)):
    if len(data) % (i+1) == 0:
      if i == 0:
        s = data[0]
      else:
        s = data[:i+1]

      if s * (len(data)//(i+1)) == data:
        res = len(data) // (i+1)
        break
    else:
      continue

  return res

data = sys.stdin.read() # 입력받음
data = data.split('\n')

for one_data in data:
  if one_data == '.':
    break
  else:
    result = solution(one_data)
    print(result)