주어진 문자열이 나쁜지 여부를 확인하는 C++ 프로그램

n개의 문자가 있는 문자열 S가 있다고 가정합니다. S는 영문 소문자와 ')' 문자를 포함합니다. 끝에 있는 문자 ')'의 수가 나머지 문자의 수보다 엄격하게 크면 문자열이 잘못된 것입니다. S가 나쁜지 아닌지 확인해야 합니다.

따라서 입력이 S ="fega)))))"와 같으면 출력은 True가 됩니다. 왜냐하면 이것은 4개의 문자와 6개의 ')가 있기 때문에 나쁘기 때문입니다.

단계

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

ans := 0
n := size of S
i := n - 1
while (i >= 0 and S[i] is same as ')'), do:
   (decrease i by 1)
z := n - 1 - i
ans := 2 * z - n
if ans > 0, then:
   return true
Otherwise
   return false

예시

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

#include <bits/stdc++.h>
using namespace std;

bool solve(string S) {
   int ans = 0;
   int n = S.size();
   int i = n - 1;
   while (i >= 0 && S[i] == ')')
      i--;
   int z = n - 1 - i;
   ans = 2 * z - n;
   if (ans > 0)
      return true;
   else
      return false;
}
int main() {
   string S = "fega))))))";
   cout << solve(S) << endl;
}

입력

"fega))))))"

출력

1