[stack]문제 - 쇠막대기

https://www.acmicpc.net/problem/10799

문제는 굉장히 어려워 보이나 규칙성을 찾는다면 스택을 이용해 간단하게 해결할 수 있는 문제이다.

입력받은 string을 순차적으로 검사해

괄호 ( 가 있다면 스택에 추가하고,

괄호 ) 가 있다면 레이저에 의한 ')'인지 쇠막대기에 의한 ')'인지확인하여 각각의 경우를 처리해주면 된다.

레이저에의한 ) 괄호 같은 경우엔 겹쳐져있는 막대기를 한번에 자르는 것이므로 스택에 남아있는 ' ( ' 의 수를 추가하면 될 것 같다.

또한 레이저가 끝났으므로 pop을 하여 앞에 남아있는 레이저의 ( 괄호 또한 삭제해준다.

쇠막대기에 의햔 ) 괄호는 쇠막대기가 끝났다는 것을 의미하므로 결과에 +1을 추가해주고, 쇠막대기의 시작을 알려주는 ( 괄호를 pop해준다.  

결과값 출력을 해주면 정답을 얻어낼 수 있다.

#include<iostream>
#include<stack>
#include<string>
using namespace std;
int valid(string n) {
    stack<int> pipe;
    int stringSize = n.size();
    int result=0;
    for (int i = 0; i < stringSize; i++) {
        if (n[i] == '(')
            pipe.push(i);
        else {
            if(pipe.top() + 1 == i) {
                pipe.pop();
                result += pipe.size();
                
            }
            else {
                pipe.pop();
                result += 1;
                
            }
        }
 
    }
    return result;
}
 
int main() {
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
 
        string what;
        cin >> what;
        int result = valid(what);
        cout << result << '\n';
 
    return 0;
}