이 자습서에서는 두 개의 배열 A와 B가 제공됩니다. 예를 들어, A[ I ]> B[ I ]에 대한 인덱스가 최대화되도록 A의 순열을 출력해야 합니다. 예를 들어
Input: A = [12, 22, 41, 13], B = [1, 20, 10, 12] Output: 12, 22, 41, 13 Input: A = [2, 5, 9, 7], B = [1, 12, 4, 54] Output: 2 7 5 9 Multiple answers can be present in that case we are simply going to print any one of the answers.
이 문제에서는 A[ i ]> B[ i ]의 인덱스를 최대화해야 하므로 탐욕스럽게 이 문제를 해결하려고 합니다.
해결책을 찾기 위한 접근 방식
이 접근 방식에서는 먼저 두 배열을 모두 정렬합니다. A[ i ]가 그것보다 더 중요하도록 배열 B의 각 인덱스를 탐욕스럽게 검사한 다음 해당 요소를 벡터에 배치합니다.
예
#include <bits/stdc++.h>
using namespace std;
int main(){
int A[] = { 2, 5, 9, 7 };
int B[] = { 1, 12, 4, 54 };
int n = sizeof(A) / sizeof(int); // size of our arrays
vector<pair<int, int> > A_pair, B_pair;
/***********************We are linking element to its position***********/
for (int i = 0; i < n; i++)
A_pair.push_back({A[i], i});
for (int i = 0; i < n; i++)
B_pair.push_back({B[i], i});
/***********************************************************************/
/*****Sorting our pair vectors********************/
sort(A_pair.begin(), A_pair.end());
sort(B_pair.begin(), B_pair.end());
int i = 0, j = 0, ans[n];
memset(ans, -1, sizeof(ans)); // initializing all the elements with value -1
vector<int> remaining; // this will store our elements which have lesser value than elemnt present in B.
while (i < n && j < n) {
// as our array is sorted then if we find any element in
//current index which has less value than B of current index then
// automatically it will have less value than other elements of B
// that's why we push such indices in remaining otherwise we push element in ans
if (A_pair[i].first > B_pair[j].first) {
ans[B_pair[j].second] = A_pair[i].first;
i++;
j++;
}
else {
remaining.push_back(i);
i++;
}
}
j = 0;
for (int i = 0; i < n; ++i){
// now if any index of answer is unchanged so that means
//we need to fill that position with the remaining elements
if (ans[i] == -1){
ans[i] = A_pair[remaining[j]].first;
j++;
}
}
for (int i = 0; i < n; i++) // printing our answer
cout << ans[i] << " ";
return 0;
} 출력
2 7 5 9
위 코드 설명
이 접근 방식에서는 먼저 모든 요소를 인덱스에 연결하여 정렬할 때 이전 인덱스를 그대로 유지합니다. 이제 우리는 쌍의 벡터를 모두 정렬하여 B_pair보다 더 우수한 값을 갖는 A_pair의 인덱스를 얻으면 두 배열을 통해 이동할 때 탐욕스럽게 답을 검색하므로 이를 배열에 저장합니다. B_pair의 위치) 그렇지 않으면 두 벡터를 모두 정렬했기 때문에 A_pair의 이 값을 사용할 수 없다는 것을 알고 있으므로 나머지 벡터의 해당 요소 인덱스를 푸시합니다. 이제 나머지를 사용하여 배열을 채웁니다. 벡터로 만든 다음 답을 인쇄합니다.
결론
이 튜토리얼에서는 다른 배열에서 더 작은 값을 가진 배열의 순열을 찾는 문제를 해결합니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 우리가 해결한 완전한 접근 방식을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 튜토리얼이 도움이 되기를 바랍니다.