두 개의 문자열 s와 t가 주어졌을 때, s가 t의 회전(rotation)인지 확인하는 문제를 살펴보겠습니다. 즉, 문자열 s를 회전시켜서 t를 만들어낼 수 있는지 판단하는 것입니다.
예를 들어 입력이 s = "helloworld", t = "worldhello"라면, s를 적절히 회전하면 t를 얻을 수 있으므로 출력은 True(1)가 됩니다.
해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 두 문자열 s0과 s1의 길이가 다르면 false를 반환합니다. 길이가 다른 문자열은 절대 회전 관계일 수 없습니다.
- s := s0 + s0 — 문자열 s0을 자기 자신과 연결합니다.
- s 안에 s1이 존재하면 true를 반환하고, 존재하지 않으면 0(false)을 반환합니다.
핵심 아이디어
이 풀이의 핵심은 문자열을 자기 자신과 한 번 이어 붙이면(s0 + s0), 원본 문자열의 모든 가능한 회전 결과가 반드시 그 안에 포함된다는 점입니다. 예를 들어 "abc"를 회전하면 "bca", "cab"가 나오는데, "abcabc" 안에는 이 세 가지가 모두 부분 문자열로 존재합니다. 따라서 별도의 회전 연산 없이 find 함수 하나만으로 판별할 수 있습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool solve(string s0, string s1) {
if(s0.size() != s1.size())
return false;
string s = s0 + s0;
return s.find(s1) != string::npos;
}
};
int main(){
Solution ob;
cout << (ob.solve("helloworld", "worldhello"));
}입력
"helloworld", "worldhello"
출력
1
복잡도 분석
시간 복잡도는 find 함수가 부분 문자열을 탐색하는 데 O(n) 시간이 걸리므로 전체적으로 O(n)입니다. 공간 복잡도는 문자열을 한 번 더 저장해야 하므로 O(n)입니다. 길이 검사를 먼저 수행하기 때문에 길이가 다른 경우에는 즉시 종료되어 불필요한 연산을 줄일 수 있습니다.