C++에서 시퀀스 증가를 위한 최소 스왑

길이가 0이 아닌 동일한 두 정수 시퀀스 A와 B가 있다고 가정합니다. 요소 A[i]와 B[i]를 교환할 수 있습니다. 두 요소가 각각의 시퀀스에서 동일한 인덱스 위치에 있다는 점을 명심해야 합니다. 일정 수의 스왑을 완료한 후 A와 B는 모두 엄격하게 증가합니다. 두 시퀀스를 엄격하게 증가시키려면 최소 스왑 수를 찾아야 합니다.

따라서 입력이 A =[1,3,5,4] 및 B =[1,2,3,7]인 경우 A[3]을 B[3]으로 바꾸면 답은 1이 됩니다. 그러면 시퀀스는 A =[1,3,5,7] 및 B =[1,2,3,4]가 되며 둘 다 엄격하게 증가합니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=배열의 크기, 각각 크기가 n인 두 개의 배열 swapCnt 및 noSwapCnt를 만듭니다.
1을 swapCnt에 삽입하고 0을 noSwapCnt에 삽입
범위 1에서 n – 1까지의 i에 대해
- swapCnt[i] :=n 및 noSwapCnt :=n
- A[i]> A[i – 1] AND B[i]> B[i – 1]이면
  - noSwapCnt[i] :=noSwapCnt[i – 1]
  - swapCnt[i] :=swapCnt[i – 1] + 1
- A[i]> B[i – 1] 및 B[i]> A[i – 1]이면
  - swapCnt[i] :=swapCnt[i]의 최소값, 1 + noSwapCnt[i – 1]
  - noSwapCnt[i] :=최소 swapCnt[i – 1], noSwapCnt[i]
최소 swapCnt[n – 1], noSwapCnt[n – 1]
반환

예시(C++)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minSwap(vector<int>& A, vector<int>& B) {
      int n = A.size();
      vector <int> swapCnt(n), noSwapCnt(n);
      swapCnt[0] = 1;
      noSwapCnt[0] = 0;
      for(int i = 1; i < n; i++){
         swapCnt[i] = n;
         noSwapCnt[i] = n;
         if(A[i] > A[i - 1] && B[i] > B[i - 1]){
            noSwapCnt[i] = noSwapCnt[i - 1];
            swapCnt[i] = swapCnt[i - 1] + 1;
         }
         if(A[i] > B[i - 1] && B[i] > A[i - 1]){
            swapCnt[i] = min(swapCnt[i], 1 + noSwapCnt[i - 1]);
            noSwapCnt[i] = min(swapCnt[i - 1], noSwapCnt[i]);
         }
      }
      return min(swapCnt[n - 1], noSwapCnt[n - 1]);
   }
};
main(){
   vector<int> v1 = {1,3,5,4};
   vector<int> v2 = {1,2,3,7};
   Solution ob;
   cout << (ob.minSwap(v1, v2));
}

입력

[1,3,5,4]
[1,2,3,7]

C++에서 시퀀스 증가를 위한 최소 스왑

예시(C++)

입력

출력