Python에서 두 문자열이 서로의 회전인지 확인하는 방법

두 개의 문자열 s와 t가 주어졌을 때, t가 s를 회전(rotation)시킨 결과인지 판별하는 문제입니다. 문자열 회전이란 문자열의 일부를 앞에서 잘라 뒤로 붙여 만든 형태를 의미합니다.

예를 들어 입력이 s = "hello", t = "llohe"라면, "hello"를 두 글자 앞부분("he")을 잘라 뒤에 붙이면 "llohe"가 되므로 출력은 True입니다.

해결 접근 방법

이 문제는 아주 간단하고 우아한 트릭으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 먼저 s와 t의 길이가 같은지 확인합니다. 길이가 다르면 회전일 수 없으므로 False를 반환합니다.
• s를 자기 자신과 이어 붙여 temp = s + s를 만듭니다.
• temp 안에 t가 존재하는지 확인합니다. 존재한다면 t는 s의 회전이므로 True를 반환하고, 그렇지 않으면 False를 반환합니다.

왜 이 방법이 작동할까?

문자열 s를 두 번 이어 붙이면 모든 가능한 회전 결과가 그 안에 반드시 포함됩니다. 예를 들어 "hello" + "hello" = "hellohello"에는 "elloh", "llohe", "lohel", "ohell" 등 모든 회전 형태가 부분 문자열로 나타납니다. 따라서 t가 s의 회전이라면 반드시 temp 안에서 발견됩니다.

예제 코드

def solve(s, t):
    if len(s) != len(t):
        return False

    temp = s + s

    if temp.count(t) > 0:
        return True
    return False

s = "hello"
t = "llohe"
print(solve(s, t))

입력

"hello", "llohe"

출력

True

복잡도 분석

시간 복잡도는 문자열 검색 연산에 의해 결정되며, 일반적으로 O(n) 수준입니다. 공간 복잡도는 s를 두 번 저장해야 하므로 O(n)입니다. 여기서 n은 문자열의 길이입니다.