설명
처음 N 숫자의 순열을 갖는 N 숫자의 배열이 주어집니다. 단일 작업으로 모든 접두사를 반전할 수 있습니다. 작업은 배열의 숫자가 오름차순으로 정렬되도록 이러한 작업의 최소 수를 찾는 것입니다.
예시
배열이 {1, 2, 4, 3}인 경우 배열을 오름차순으로 정렬하려면 최소 3단계가 필요합니다. -
- 전체 배열 반전 {3, 4, 2, 1}
- 처음 두 요소 반전 {4, 3, 2, 1}
- 전체 배열 {1, 2, 3, 4} 반전
알고리즘
- 주어진 숫자를 문자열로 인코딩합니다. 배열을 정렬하고 문자열 대상으로 인코딩합니다.
- 그런 다음 초기 순열에서 BFS를 수행합니다. 매번 현재 순열의 접두어를 반대로 하여 유도된 모든 순열을 확인합니다.
- 방문하지 않은 경우 반전 횟수와 함께 대기열에 넣습니다.
- 인코딩된 문자열의 순열이 대상 문자열과 동일한 경우 여기에 도달하는 데 필요한 반전 횟수를 반환합니다.
- 즉, 문자열의 모든 순열이 완료되고 그 중 최소값이 답으로 반환됩니다.
예시
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int minimumPrefixReversals(int *a, int n) {
string start = "";
string destination = "", t, r;
for (int i = 0; i < n; i++) {
start += to_string(a[i]);
}
sort(a, a + n);
for (int i = 0; i < n; i++) { destination += to_string(a[i]);
}
queue<pair<string, int> > qu;
pair<string, int> p;
qu.push(make_pair(start, 0));
if (start == destination) {
return 0;
}
while (!qu.empty()) {
p = qu.front();
t = p.first;
qu.pop();
for (int j = 2; j <= n; j++) {
r = t;
reverse(r.begin(), r.begin() + j);
if (r == destination) {
return p.second + 1;
}
qu.push(make_pair(r, p.second + 1));
}
}
}
int main() {
int a[] = { 1, 2, 4, 3 };
int n = sizeof(a) / sizeof(a[0]);
cout << "Minimum reversal: " << minimumPrefixReversals(a, n) << endl;
return 0;
} 출력
위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다 -
Minimum reversal: 3