사전 순으로 최소 문자열 회전

문자열이 주어진다고 가정해 보겠습니다. 문자열이 일련의 문자라는 것을 알고 있습니다. 사전순 회전은 문자열을 회전하여 사전순으로 문자를 변환하는 것입니다.

해결 방법은 간단합니다. 주어진 문자열을 자신과 연결하기만 하면 다른 배열에 문자열의 모든 회전이 저장됩니다. 배열을 오름차순으로 정렬한 후 가장 낮은 값이 최종 결과입니다.

입력 및 출력

Input:
The String “BCAAFAABCD”
Output:
Rotated String: “AABCDBCAAF”

알고리즘

minStrRotation(str)

입력 - 주어진 문자열입니다.

출력 - 최소 문자열 회전이 필요합니다.

Begin
   n := length of str
   define strArr to store all rotations
   tempStr := concatenate str with str again

   for i := 0 to n, do
      strArr[i] := substring of tempStr from (i to n)
   done

   sort the strArr
   return strArr[0]
End

예시

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

string minStrRotation(string str) {
   int n = str.size();
   string strArray[n];    //array to store all rotations of str
   string tempStr = str + str;    //concatinate str two times

   for (int i = 0; i < n; i++)
      strArray[i] = tempStr.substr(i, n);    //get sub string from ith index to nth index
   sort(strArray, strArray+n);
   return strArray[0];    //The first index is the result
}

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

출력

Enter String: BCAAFAABCD
Rotated String: AABCDBCAAF