Python에서 문자열 반복으로 다른 문자열을 만들 수 있는지 확인하는 방법

두 개의 문자열 s와 t가 주어졌을 때, 문자열 s를 몇 번 이어 붙여야(반복해야) 문자열 t를 만들 수 있는지 구하는 문제입니다. 만약 s를 아무리 반복해도 t를 생성할 수 없다면 -1을 반환합니다.

예를 들어 s = "tom", t = "tomtomtom"이라고 가정해 보겠습니다. 이 경우 "tom"을 3번 이어 붙이면 "tomtomtom"이 되므로 출력 결과는 3입니다.

문제 해결 접근 방식

이 문제는 다음 단계를 따라 해결할 수 있습니다.

• t의 길이가 s의 길이로 나누어 떨어지지 않으면
  • -1을 반환합니다.
• cnt := (t의 길이 ÷ s의 길이)의 몫을 계산합니다.
• s를 cnt번 반복하여 새로운 문자열을 만듭니다.
• 반복한 문자열이 t와 같다면
  • cnt를 반환합니다.
• 그렇지 않으면 -1을 반환합니다.

핵심 아이디어는 간단합니다. t가 s의 반복으로만 구성되어 있다면, t의 길이는 반드시 s의 길이의 배수여야 합니다. 따라서 먼저 길이 조건을 확인하고, 그 후 실제로 반복한 결과가 t와 일치하는지 검증하면 됩니다.

구현 예제

아래 코드를 통해 더 자세히 이해해 보겠습니다.

def solve(s, t):
    # t의 길이가 s의 길이로 나누어 떨어지지 않으면 -1 반환
    if(len(t) % len(s) != 0):
        return -1
    # 필요한 반복 횟수 계산
    cnt = int(len(t) / len(s))
    # s를 cnt번 반복
    s = s * cnt
    # 반복한 결과가 t와 같은지 확인
    if(s == t):
        return cnt
    return -1

s = "tom"
t = "tomtomtom"
print(solve(s, t))

입력

"tom", "tomtomtom"

출력

3

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(n)입니다. 여기서 n은 문자열 t의 길이입니다. 문자열 비교와 반복 연산 모두 문자열 길이에 비례하는 시간이 소요되기 때문입니다. 공간 복잡도 역시 반복된 문자열을 저장해야 하므로 O(n)입니다.