[BOJ 11899] 괄호 끼워넣기

올바른 괄호열의 가장 큰 특징으로 "닫는 괄호는 반드시 여는 괄호보다 나중에 나와서 쌍을 이뤄야 한다."가 있다. 이는 닫는 괄호가 먼저 나온다면 앞에 여는 괄호를 무조건 붙여야 한다는 의미이다. 나머지는 괄호가 쌍을 이룰 때마다 처리해주면 된다. 마지막에 스택에 남아있는 여는 괄호들의 뒤에 닫는 괄호를 모두 붙여야 한다는 것을 유의하자.

 

string str;
stack<char> s;
int ans;

int main(void) {
    fastio;
    cin >> str;
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == '(') s.push(str[i]);
        else {
            if (s.empty())
                ans++;
            else s.pop();
        }
    }
    ans += s.size();
    cout << ans << "\n";
    return 0;
}