Educational Codeforces Round 98 (Rated for Div. 2) - C번

codeforces.com/contest/1452/problem/C

Problem - C - Codeforces

기초적인 stack 문제였다.

괄호의 짝을 stack을 사용해서 구하는 문제는 기초중의 기초니까 꼭 알고 넘어가자.

 

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
typedef long long ll;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    string str;
    cin >> t;
    while (t--) {
        cin >> str;
        stack<char>s;
        for (int i = 0; i < str.size(); i++) {
            s.push(str[i]);
        }
        int left_s = 0, right_s = 0, left_b = 0, right_b = 0;
        int ans = 0;
        while (!s.empty()) {
            char temp = s.top();
            s.pop();
            if (temp == ')') {
                if (left_s == 0) right_s++;
                else{
                    left_s--;
                    ans++;
                }
            }
            else if (temp == '(') {
                if (right_s > 0) {
                    right_s--;
                    ans++;
                }
            }
            else if (temp == ']') {
                if (left_b == 0) right_b++;
                else {
                    left_b--;
                    ans++;
                }
            }
            else {
                if (right_b > 0) {
                    right_b--;
                    ans++;
                }
            }
        }
        cout << ans << "\n";
    }
}