C++에서 k 위와 같은 동일한 수의 요소를 얻기 위해 하위 목록을 제거하는 프로그램

nums라는 숫자 목록과 또 다른 숫자 k가 있다고 가정하면 목록에서 최대 한 번만 하위 목록을 제거할 수 있습니다. k보다 엄격하게 작은 숫자와 k보다 큰 숫자의 양이 같도록 가장 긴 결과 목록의 길이를 찾아야 합니다.

따라서 입력이 nums =[6, 10, 8, 9, 3, 5], k =6과 같으면 출력은 5가 됩니다. 마치 하위 목록 [9]를 제거하면 [6, 10, 8, 3, 5] 그리고 6보다 작은 두 개의 숫자[3, 5]와 6보다 큰 두 개의 숫자[10, 8]가 있습니다.

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

• nums + 1과 같은 크기의 배열 v를 정의하고 0으로 채움
• cnt :=0
• 초기화 i의 경우:=0, i <숫자의 크기일 때 업데이트(i를 1만큼 증가), 수행 -
  • nums[i]
  • (cnt를 1씩 증가)
• 그렇지 않으면 nums[i]> k일 때:
  • (cnt를 1씩 감소)
• v[i + 1] =cnt

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

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int solve(vector<int>& nums, int k) {
      vector<int> v(nums.size() + 1, 0);
      int cnt = 0;
      for (int i = 0; i < nums.size(); ++i) {
         if (nums[i] < k)
            ++cnt;
         else if (nums[i] > k)
            --cnt;
         v[i + 1] = cnt;
      }
      if (v.back() == 0) return int(nums.size());
      int delta = v.back();
      map<int, int> m;
      int ans = INT_MAX;
      for (int i = 1; i <= v.size(); ++i) {
         if (m[v[i] - v.back()] != 0 || v[i] - v.back() == 0) {
            ans = min(ans, i - m[v[i] - v.back()]);
         }
         m[v[i]] = i;
      }
      if (ans == INT_MAX)
         return 0;
      else
         return int(nums.size() - ans);
   }
};
main(){
   Solution ob;
   vector<int> v = {6, 10, 8, 9, 3, 5};
   int k = 6;
   cout << ob.solve(v, k); }

입력

{6, 10, 8, 9, 3, 5}, 6

출력

5