C++에서 최대 수 만들기

두 개의 숫자를 나타내는 0-9의 숫자를 가진 길이가 m과 n인 두 개의 배열이 있다고 가정합니다. 두 자리의 자릿수에서 m + n보다 작은 길이 k의 최대 수를 만들어야 합니다. 동일한 배열에서 숫자의 상대적 순서는 보존되어야 한다는 점을 명심해야 합니다. k 자리의 배열을 찾아야 합니다. 따라서 입력이 [3,4,7,5] 및 [9,1,3,5,8,4]이고 k =5인 경우 답은 [9,8,7,5,4 ].

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

• mergeThem() 함수를 정의하면 배열 nums1, 배열 nums2,
• ret 배열 정의
• i :=0, j :=0, n :=nums1의 크기, m :=nums2의 크기
• 동안(i
• Great(nums1, nums2, i, j) 함수 호출이 true이면 -
  • ret 끝에 nums1[i] 삽입
  • (i를 1씩 증가)
• 그렇지 않으면
  • ret 끝에 nums2[j] 삽입
  • (j를 1씩 증가)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<int> mergeThem(vector<int> nums1, vector<int> nums2)
   {
      vector<int> ret;
      int i = 0;
      int j = 0;
      int n = nums1.size();
      int m = nums2.size();
      while (i < n || j < m) {
         if (greater(nums1, nums2, i, j)) {
            ret.push_back(nums1[i]);
            i++;
         }
         else {
            ret.push_back(nums2[j]);
            j++;
         }
      }
      return ret;
   }
   vector<int> modify(vector<int>& v, int k)
   {
      stack<int> st;
      vector<int> ret;
      for (int i = 0; i < v.size(); i++) {
         int x = v[i];
         while (!st.empty() && st.top() < x && st.size() + (v.size() - i) - 1 >= k) {
            st.pop();
         }
         if (st.size() < k)
            st.push(x);
         }
         while (!st.empty()) {
            ret.push_back(st.top());
            st.pop();
         }
         reverse(ret.begin(), ret.end());
         return ret;
      }
      bool greater(vector<int>& a, vector<int>& b, int i, int j)
      {
         while (i < a.size() && j < b.size() && a[i] == b[j])
         i++, j++;
         return j == b.size() || (i < a.size() && a[i] > b[j]);
      }
      vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k)
      {
         vector<int> ret;
         int n = nums1.size();
         int m = nums2.size();
         for (int i = 0; i <= k; i++) {
            if (i <= n && (k - i) <= m) {
               vector<int> candidate = mergeThem(modify(nums1, i), modify(nums2, k - i));
               if (greater(candidate, ret, 0, 0)) {
                  ret = candidate;
               }
            }
         }
         return ret;
     }
};
main() {
   Solution ob;
   vector<int> v = { 3, 4, 7, 5 }, v1 = { 9, 1, 3, 5, 8, 4 };
   print_vector(ob.maxNumber(v, v1, 5));
}

입력

{ 3, 4, 7, 5 }
{ 9, 1, 3, 5, 8, 4 }
5

출력

[9, 8, 7, 5, 4, ]