두 문자열이 서로 회전 관계인지 확인하는 C++ 프로그램

이번 글에서는 두 문자열이 서로 회전(rotation) 관계에 있는지 판별하는 프로그램을 살펴보겠습니다.

문자열의 회전이란 다음과 같은 개념입니다. 예를 들어 S1 = 'HELLO', S2 = 'LOHEL'이라는 두 문자열이 있다고 가정해 봅시다. 'HELLO'를 왼쪽으로 3칸 회전시키면 'LOHEL'이 되므로, 이 두 문자열은 서로 회전 관계라고 할 수 있습니다.

해결 아이디어

이 문제는 의외로 간단하게 해결할 수 있습니다. 첫 번째 문자열을 자기 자신과 한 번 더 연결(concatenate)한 뒤, 그 결과 문자열 안에 두 번째 문자열이 포함되어 있는지만 확인하면 됩니다.

'HELLO'를 자기 자신과 연결하면 HELLOHELLO가 됩니다. 이렇게 만들어진 문자열 [HELLOHELLO] 안에는 'LOHEL'이 포함되어 있으므로 두 문자열이 회전 관계임을 바로 알 수 있습니다. 어떤 회전 문자열이든 원본 문자열을 두 배로 늘린 문자열 안에는 반드시 등장하기 때문입니다.

알고리즘

isRotation(str1, str2)

시작
    str1과 str2의 길이가 다르면 false를 반환
    temp := str1을 str1 자기 자신과 연결
    만약 temp가 str2를 포함하고 있다면
        true를 반환
    그렇지 않으면 false를 반환
종료

C++ 구현 예제

#include<iostream>
using namespace std;
bool isRotation(string str1, string str2){
    if(str1.length() != str2.length())
        return false;
    string con_str = str1 + str1;
    if(con_str.find(str2) != string::npos){
        return true;
    } else {
        return false;
    }
}
main() {
    string str1, str2;
    cout << "Enter two strings: ";
    cin >> str1 >> str2;
    if(isRotation(str1, str2)){
        cout << "Two strings are rotation of each other";
    } else {
        cout << "Two strings are not rotation of each other";
    }
}

실행 결과

Enter two strings: STACK CKSTA
Two strings are rotation of each other

'STACK'을 왼쪽으로 회전시키면 'CKSTA'를 만들 수 있으므로, 프로그램은 두 문자열이 회전 관계라고 정확하게 판별했습니다.

마무리

먼저 두 문자열의 길이를 비교해 다르면 즉시 종료하므로 불필요한 연산을 줄일 수 있습니다. 추가로 필요한 메모리는 문자열 하나 크기(O(n))이며, 전체 실행 시간은 내부적으로 사용되는 부분 문자열 검색 방식에 따라 결정됩니다. KMP와 같은 효율적인 문자열 검색 알고리즘을 함께 활용하면 더 큰 입력에서도 좋은 성능을 기대할 수 있습니다.