C++로 주어진 문자열이 나쁜(bad) 문자열인지 판별하는 방법

n개의 문자로 이루어진 문자열 S가 있다고 가정해 봅시다. S는 소문자 영어 알파벳과 ')' 문자로만 구성되어 있습니다. 문자열 끝부분에 연속해서 나타나는 ')'의 개수가 나머지 문자의 개수보다 엄격하게 많을 때, 이 문자열을 "나쁜(bad)" 문자열이라고 정의합니다. 우리의 목표는 주어진 문자열 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:
    (i를 1씩 감소)
z := n - 1 - i
ans := 2 * z - n
if ans > 0, then:
    return true
Otherwise
    return false

이 알고리즘의 핵심 아이디어는 다음과 같습니다. 먼저 문자열 끝에서부터 연속된 ')'의 개수(z)를 센 뒤, 2 × z가 전체 길이 n보다 큰지 확인합니다. 2z > n이라는 조건은 곧 z > n − z, 즉 끝에 붙은 ')'의 개수가 나머지 문자의 개수보다 많다는 의미이며, 이 경우 해당 문자열은 나쁜 문자열입니다.

예제

아래 구현 예시를 통해 좀 더 쉽게 이해해 보겠습니다.

#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))))))"