사전순 최소 문자열 회전 알고리즘: 개념부터 C++ 구현까지

사전순 최소 문자열 회전이란?

문자열은 문자들이 나열된 시퀀스입니다. 여기서 사전순 회전(Lexicographical Rotation)이란, 문자열을 여러 방식으로 회전시켰을 때 그중 결과 문자열이 사전순(lexicographical order)으로 가장 앞서는 회전을 찾는 문제를 의미합니다.

예를 들어 문자열 "BCAAFAABCD"를 한 칸씩 밀어가며 만들 수 있는 모든 회전 형태 중에서, 사전순으로 가장 작은 문자열이 무엇인지 찾는 것이 목표입니다.

해결 접근 방법

이 문제의 해법은 의외로 간단합니다. 핵심 아이디어는 다음과 같습니다.

주어진 문자열을 자기 자신과 한 번 더 이어 붙인 뒤, 가능한 모든 회전 형태를 별도의 배열에 저장합니다. 그리고 배열을 오름차순으로 정렬하면, 배열의 첫 번째 요소가 곧 사전순으로 가장 작은 회전 문자열, 즉 최종 결과가 됩니다.

문자열을 두 배로 늘려 놓으면 길이 n인 모든 회전이 길이 n짜리 부분 문자열 형태로 포함되기 때문에, 별도의 회전 연산 없이 substr 함수만으로 모든 회전을 손쉽게 얻을 수 있다는 점이 이 방법의 장점입니다.

입력 및 출력 예시

입력:
문자열 "BCAAFAABCD"

출력:
회전된 문자열: "AABCDBCAAF"

알고리즘

minStrRotation(str)

입력 − 주어진 문자열.

출력 − 사전순으로 가장 작은 회전 문자열.

시작
   n := str의 길이
   모든 회전을 저장할 배열 strArr 선언
   tempStr := str을 두 번 이어 붙인 문자열

   i := 0부터 n-1까지 반복
      strArr[i] := tempStr에서 i번째부터 n글자에 해당하는 부분 문자열
   반복 끝

   strArr을 오름차순 정렬
   return strArr[0]
끝

C++ 구현 예제

#include <iostream>
#include <algorithm>
using namespace std;

string minStrRotation(string str) {
   int n = str.size();
   string strArray[n];   // str의 모든 회전을 저장하는 배열
   string tempStr = str + str;   // str을 두 번 이어 붙임

   for (int i = 0; i < n; i++)
      strArray[i] = tempStr.substr(i, n);   // i번째 인덱스부터 길이 n만큼 부분 문자열 추출
   sort(strArray, strArray + n);
   return strArray[0];   // 정렬 후 첫 번째 원소가 결과
}

int main() {
   string str;
   cout << "Enter String: "; cin >> str;
   cout << "Rotated String: " << minStrRotation(str);
}

실행 결과

Enter String: BCAAFAABCD
Rotated String: AABCDBCAAF

시간 및 공간 복잡도 분석

길이가 n인 문자열에 대해 총 n개의 회전을 생성하므로 부분 문자열 추출에는 O(n²)의 시간이 걸립니다. 이후 정렬 단계에서 서로 다른 문자열 간 비교가 최대 O(log n)번 수행되고, 각 비교는 길이 n의 문자열 비교이므로 전체 시간 복잡도는 O(n² log n)입니다.

공간 복잡도 역시 n개의 길이 n짜리 문자열을 저장해야 하므로 O(n²)입니다.

참고로, 더 큰 입력에 대해서는 Booth 알고리즘(O(n))이나 Duval 알고리즘 기반의 선형 시간 해법을 사용하면 훨씬 효율적으로 최소 회전을 찾을 수 있습니다. 위에서 소개한 방법은 구현이 직관적이고 이해하기 쉬워 학습용으로 적합합니다.