주어진 이진 문자열에서 최소 올바른 문자열을 찾는 C++ 코드

<시간/>

n 비트가 있는 이진 문자열 S가 있다고 가정합니다. 중복되는 선행 0은 없습니다. S −

에 대해 두 가지 다른 작업을 수행할 수 있습니다.

인접한 비트 쌍을 교환합니다.
"11"을 모두 "1"로 바꾸기

val(S)가 S의 10진수 표현이라고 하자. val(A) 일 때 올바른 문자열 A가 다른 올바른 문자열 'B'보다 작은 올바른 최소 문자열을 찾아야 합니다.

따라서 입력이 S ="1001"과 같으면 출력은 100이 됩니다. "1001" -> "1010" -> "1100" -> "100"과 같은 작업을 수행할 수 있기 때문입니다.

단계

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

n := size of S
res := a blank string
res := res + S[0]
for initialize i := 1, when i < n, update (increase i by 1), do:
   if S[i] is same as '0', then:
      res := res concatenate "0"
return res

예시

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

#include <bits/stdc++.h>
using namespace std;
string solve(string S){
   int n = S.size();
   string res = "";
   res += S[0];
   for (int i = 1; i < n; i++){
      if (S[i] == '0'){
         res += "0";
      }
   }
   return res;
}
int main(){
   string S = "1001";
   cout << solve(S) << endl;
}

입력

"1001"