BaekJoon(9012)::괄호

문제

9012번: 괄호

문제파악

괄호문자열(Parenthesis String,PS)은 두 개의 괄호 기호인 '('와 ')'로 구성된 문자열.

그 괄호 모양이 잘 닫혀져 있으면 올바른 문자열은(Valid PS, VPS)라고 부른다.

 

예를 들어 '(()())' 그리고 '((()))' 등은 vps지만 '(()(' 혹은'(()' 등은 vps를 만족하지 못한다.

• '(' 그리고 ')'로 구성된 문자열 : VPS
• 두개의 vps로 접합된 문자열 또한 VPS 만족
• 하나의 괄호로 둘러싼 VPS는 VPS를 만족

문제풀이

해당 문제의 경우 곰곰히 생각해보면 앞에서 부터 하나씩 stack에 넣어보면 문제가 해결 될 수 있다.

'('의 경우 앞의 문자와 상관없이 넣어주고 ')'의 경우 stack의 top이 '('이면 빼주고 비었거나 '('이 아니라면 stack에 넣어주면 된다.

 

그리고 마지막으로 stack의 사이즈를 확인해 0이면 VPS를 만족한다고 볼 수 있을 것 같다.

#include<iostream>
#include<stack>
#include<string>
using namespace std;


int main() {
	int n;
    cin >>n;

    while (n--) {
        stack<char> st;

        string vps;
        cin >> vps;

        for (int i = 0; i < vps.length();i++) {
            if (vps[i] == '(') st.push('(');

            if (vps[i] == ')') {
                if (st.empty()) st.push(')');
                if (st.top() == '(') st.pop();
            }
        }

         string result = st.empty() ? "YES" : "NO";
         cout << result << endl;
    }
    
	return 0;
}

tip...(?) 참고로 나의 경우 ')'일 때 스택이 빈 경우만 고려했는데 이유는 스택의 top이 ')'인 경우는 어차피 VPS를 만족 못하기 때문에 굳이 추가로 넣어줄 필요가 없어 생략했다.