문제 설명
서로 순열인 n개의 문자열이 주어집니다. 문자열의 첫 번째 문자를 끝으로 이동하는 작업으로 모든 문자열을 동일하게 만들어야 합니다.
예시
arr[] ={“abcd”, “cdab”}이면 2번의 이동이 필요합니다.
- 첫 번째 문자열 "abcd"를 사용하겠습니다. 문자열의 끝으로 '문자'를 이동합니다. 이 작업 문자열이 "bcda"가 된 후
- 이제 'b' 문자를 문자열 끝으로 이동합니다. 이 작업 후에 문자열은 "cdb"가 됩니다. 그러면 두 문자열이 동일하게 됩니다.
알고리즘
- 첫 번째 문자열을 가져옵니다. 'str1'이라고 부르겠습니다.
-
다음과 같이 str1을 str1에 연결하여 임시 문자열을 만듭니다. -
온도 =str1 + str1
- 다른 모든 문자열을 현재 대상과 동일하게 만드는 데 필요한 회전 수
- 모든 문자열에 대해 위의 단계를 반복하고 모든 개수의 최소값을 반환합니다.
예시
#include <iostream>
#include <string>
#include <algorithm>
#include <climits>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int minMoves(string str[], int n) {
int minCnt = INT_MAX;
for (int i = 0; i < n; ++i) {
int cnt = 0;
for (int j = 0; j < n; ++j) {
string temp = str[j] + str[j];
int index = temp.find(str[i]);
if (index != string::npos) {
cnt += index;
}
}
minCnt = min(cnt, minCnt);
}
return minCnt;
}
int main() {
string str[] = {"abcd", "cdab", "bacd", "cdba"};
cout << "Minimum moves: " << minMoves(str, SIZE(str)) << endl;
return 0;
} 출력
위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다 -
Minimum moves: 2