문제 개요
주어진 문자열에 대해, 회전(rotation)을 반복 수행했을 때 원래 문자열과 다시 동일해지기까지 필요한 최소 회전 횟수를 구하는 문제입니다.
예시
입력 문자열이 "bbbbb"라면 모든 문자가 동일하므로 한 번만 회전해도 원래 문자열과 같아집니다. 따라서 최소 회전 횟수는 1입니다.
핵심 아이디어와 알고리즘
이 문제의 핵심은 원본 문자열을 자기 자신과 이어 붙인 문자열(s + s) 안에는 원본 문자열의 모든 회전 형태가 포함되어 있다는 사실입니다. 이를 활용하면 각 인덱스에서 부분 문자열을 잘라 원본과 비교하는 방식으로 최소 회전 횟수를 쉽게 찾을 수 있습니다.
- 결괏값(result)을 0으로 초기화합니다.
- 원본 문자열을 자기 자신과 연결한 임시 문자열을 만듭니다.
- 임시 문자열에서 두 번째 문자, 즉 인덱스 1부터 시작하여 원본 문자열과 같은 길이의 부분 문자열을 추출합니다.
- 카운터를 증가시킵니다.
- 추출한 부분 문자열이 원본 문자열과 일치하는지 확인합니다. 일치하면 루프를 종료하고, 그렇지 않으면 다음 인덱스부터 과정을 반복합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int getRotationCount(string str) {
string temp = str + str;
int n = str.length();
for (int i = 1; i <= n; ++i) {
string sub = temp.substr(i, str.size());
if (str == sub) {
return i;
}
}
return n;
}
int main() {
string str = "bbbbb";
cout << "Rotation count = " << getRotationCount(str) << endl;
return 0;
}위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.
실행 결과
Rotation count = 1
복잡도 분석
- 시간 복잡도: O(n²) — 최대 n개의 시작 위치마다 길이 n의 부분 문자열을 비교하기 때문입니다.
- 공간 복잡도: O(n) — 원본 문자열을 두 배 길이로 이어 붙인 임시 문자열을 저장해야 합니다.