C++의 두 배열에서 고유 쌍 최대화

문제 설명

크기가 N인 두 개의 배열이 주어졌을 때, 각 배열의 요소가 최대 한 번 사용되고 선택한 배열 간의 절대 차이가 되도록 첫 번째 배열과 두 번째 배열의 요소를 사용하여 최대 쌍 수를 형성합니다. 쌍을 형성하는 데 사용되는 요소가 주어진 요소 K보다 작거나 같습니다.

예시

입력이 -

arr1[] ={3, 4, 5, 2, 1}

arr2[] ={6, 5, 4, 7, 15}

k =3이면 절대 차이가 3 -

(1, 4), (2, 5), (3, 6), (4, 7)

알고리즘

이 문제를 해결하기 위해 재귀적 접근 방식을 사용할 수 있습니다.

• 두 배열 모두 정렬
• 쌍을 형성하는 것이 가능한 경우 첫 번째 배열의 각 요소를 가능한 쌍에 대한 두 번째 배열의 각 요소와 비교
• 첫 번째 배열의 다음 요소에 대해 다음 가능한 쌍을 계속 확인합니다.

예시

이제 예를 살펴보겠습니다 -

#include <bits/stdc++.h>
using namespace std;
int getMaxUniquePairs(int *arr1, int *arr2, int n, int k) {
   sort(arr1, arr1 + n);
   sort(arr2, arr2 + n);
   bool visited[n];
   memset(visited, false, sizeof(visited));
   int pairCnt = 0;
   for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
         if (abs(arr1[i] - arr2[j]) <= k &&
         visited[j] == false) {
            ++pairCnt;
            visited[j] = true;
            break;
         }
      }
   }
   return pairCnt;
}
int main() {
   int arr1[] = {3, 4, 5, 2, 1};
   int arr2[] = {6, 5, 4, 7, 15};
   int n = sizeof(arr1) / sizeof(arr1[0]);
   int k = 3;
   cout << "Maximum unique pairs = " << getMaxUniquePairs(arr1, arr2, n, k) << endl;
   return 0;
}

출력

Maximum unique pairs = 4