C++의 특수 이진 문자열

공간 이진 문자열이 있다고 가정합니다. 이 문자열에는 다음과 같은 몇 가지 속성이 있습니다. -

• 0과 1의 개수는 같습니다.

• 이진 문자열의 모든 접두사는 최소한 1과 0을 포함합니다.

이제 특수 문자열 S가 있다고 가정하고 이동은 실제로 S의 비어 있지 않은 두 개의 연속적인 특수 하위 문자열을 선택하고 교체하는 것입니다.

여러 이동이 끝나면 사전순으로 가장 큰 결과 문자열을 찾아야 합니다.

따라서 입력이 11011000과 같으면 출력은 11100100이 됩니다. 그 이유는 다음과 같습니다. 부분 문자열 "10"과 "1100"이 바뀌었습니다. 이것은 몇 번의 이동 후에 가능한 사전순으로 가장 큰 문자열입니다.

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

• makeLargestSpecial() 함수를 정의하면 s가 필요합니다.

• ret :=빈 문자열

• 문자열의 배열 v 정의

• 나는 :=0

• 초기화 j :=0, cnt :=0, j

  • s[j]가 '1'과 같으면 -

    • (cnt를 1씩 증가)

  • 그렇지 않으면

    • (cnt를 1만큼 감소)

  • cnt가 0과 같으면 -

    • v의 끝에 "1" + makeLargestSpecial(인덱스 i + 1에서 j - i - 1까지의 s의 부분 문자열) 삽입

    • 나는 :=j + 1

• 배열 v.r

  정렬

• initialize i :=0의 경우 i

  • 렛 :=렛 + v[i]

• 리턴 렛

• 기본 메서드에서 문자열과 함께 makeLargestSpecial()을 호출합니다.

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

예

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string makeLargestSpecial(string s) {
      string ret = "";
      vector<string> v;
      int i = 0;
      for (int j = 0, cnt = 0; j < s.size(); j++) {
         if (s[j] == '1') {
            cnt++;
         }
         else
         cnt--;
         if (cnt == 0) {
            v.push_back("1" + makeLargestSpecial(s.substr(i + 1,
            j - i - 1)) + "0");
            i = j + 1;
         }
      }
      sort(v.rbegin(), v.rend());
      for (int i = 0; i < v.size(); i++)
      ret += v[i];
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.makeLargestSpecial("11011000"));
}

입력

11011000

출력

11100100