두 개의 문자열 A와 B가 있다고 가정해 봅시다. 이때 문자열 A를 회전시켜 가면서 어느 시점에서라도 B와 일치하는지 확인하고, 일치한다면 True를, 그렇지 않다면 False를 반환하는 문제입니다.
예를 들어 A = 'abcde', B = 'bcdea'라고 할 때, A를 왼쪽으로 한 칸 회전하면 'bcdea'가 되므로 결과는 True입니다.
문제 해결 접근 방법
이 문제는 다음 단계에 따라 해결할 수 있습니다.
- A와 B가 모두 빈 문자열이라면
True를 반환합니다. - A와 B의 길이가 다르다면 회전으로 같아질 수 없으므로
False를 반환합니다. - A를 자기 자신과 이어 붙여(A = A + A) 새로운 A를 만듭니다. 이렇게 하면 연결된 문자열 안에 A의 모든 회전 형태가 포함됩니다.
- 포인터 i와 j를 각각 0으로 초기화한 뒤, i가 A의 길이보다 작은 동안 아래 과정을 반복합니다.
- A의 남은 길이(len(A) - i + 1)가 B의 길이보다 짧으면 더 이상 매칭이 불가능하므로
False를 반환합니다. - i가 A의 범위 내에 있고, j가 B의 범위 내에 있으며, A[i] == B[j]인 동안 i와 j를 각각 1씩 증가시킵니다.
- j가 B의 길이와 같아졌다면 B 전체가 매칭된 것이므로
True를 반환합니다. - j가 0이 아니라면(부분 매칭이 있었다면) i를 1 감소시켜 위치를 보정합니다.
- j를 0으로 초기화하고, i를 1 증가시켜 다음 위치부터 탐색을 계속합니다.
- A의 남은 길이(len(A) - i + 1)가 B의 길이보다 짧으면 더 이상 매칭이 불가능하므로
파이썬 구현 예제
아래 코드를 통해 실제 구현 방법을 더 쉽게 이해할 수 있습니다.
class Solution(object):
def rotateString(self, A, B):
if not A and not B:
return True
if len(A) != len(B):
return False
A = A*2
i = 0
j = 0
while i < len(A):
if len(A)-i+1 < len(B):
return False
while i<len(A) and j < len(B) and A[i] == B[j]:
i+=1
j+=1
if j == len(B):
return True
if j:
i-=1
j=0
i+=1
ob1 = Solution()
print(ob1.rotateString("abcde", "cdeab"))입력
"abcde" "cdeab"
출력
True
핵심 포인트 정리
이 알고리즘의 핵심은 문자열을 자기 자신과 한 번 이어 붙이면 모든 회전 결과가 부분 문자열로 포함된다는 성질입니다. 실무에서는 파이썬의 in 연산자를 사용해 B in A + A 한 줄로도 같은 결과를 얻을 수 있지만, 위 구현은 매칭 과정을 직접 제어하며 동작 원리를 명확히 보여준다는 장점이 있습니다. 시간 복잡도는 최악의 경우 O(n²)이며, KMP 같은 문자열 매칭 알고리즘을 적용하면 O(n)까지 개선할 수 있습니다.