5432. 쇠막대기 자르기

5432. 쇠막대기 자르기

이 문제는 스택을 이용하여 문제를 풀 수 있었다.

주어진 문자를 하나씩 순서대로 스택에 담아가면서, ) 이게 나오면 스택에서 팝을 시켜준다. 이때 스택에 남아있는 원소들의 갯수가 잘려진 쇠

막대기들의 갯수가 된다. 하지만 고려해야할 예외사항이 있다.

( ) 나왔을 경우와 ) ) 나왔을 경우는 다른 케이스이기 때문이다.

( ) 나온 경우에는 위의 방식대로 지금까지 모든 막대가 레이저에 의해서 잘리는 경우이므로 스택의 사이즈만큼 정답에 더해준다.

) ) 나온 경우에는 레이저에 의해 잘리는게 아닌, 막대기의 길이가 끝나서 생기는 것이므로 길이가 끝나는 막대 1개를 정답에 더해준다.

<정답 코드>

#include<iostream>
#include<string>
#include<stack>
using namespace std;
 
int N, M;
 
int main()
{
    //freopen("input.txt", "r", stdin);
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        stack<char> st;
        string str;
        int ans = 0;
        cin >> str;
 
        int size = str.size();
        char before = '\0';
        for (int i = 0; i < size; i++)
        {
            if (str[i] == '(')
            {
                st.push(str[i]);
            }
            else
            {
                st.pop();
                if (before == '(')
                    ans += st.size();
                else
                    ans += 1;
            }
            before = str[i];
        }
 
 
        cout << "#" << t << " "  <<ans<< endl;
    }
 
    return 0;
}