[C++] 백준(BOJ) 9012 괄호 (VPS-Valid Parenthesis String)

전형적인 스택 문제인 괄호 문자열 판별

풀이1(내 풀이)

• c++ 의 STL 을 사용하여 풀었다.
• 스택에서 pop을 할때는 해당 스택이 비어있는지 확인하는 것이 중요하다 - 이것땜에 처음에 오류남

#include <iostream>
#include <vector>
#include <stack>
#include <string>
using namespace std;
bool isVPS(string & s)
{
	stack<char> ch;
	bool valid = true;
	for (int i = 0; i < s.length(); i++)
	{
		if (s[i] == '(')
			ch.push('(');
		else if (s[i] == ')')
		{
			if (!ch.empty())
				ch.pop();
			else
				valid = false;
		}
		else
			valid = false;
	}
	if (ch.size() != 0)
		valid = false;
	return valid;

}

int main() {

	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		string in;
		cin >> in;
		if (isVPS(in))
			cout << "YES\n";
		else
			cout << "NO\n";
	}

	return 0;
}

 

풀이2 (다른 사람)

• 스택이 비어있는 경우를 따로 조건문으로 빼서 조건을 상세하게 설정했다.

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main() {
    int testcase;
    cin >> testcase; // 몇 번 돌지 입력받음
   
    while(testcase--) {
        stack<char> st;
        string s;
        cin >> s; // 괄호들을 문자열로 입력
        
        for(int j = 0; j < s.length(); j++) {
            if(st.empty()) { //스택이 비어있다면 push
                st.push(s[j]);
            }
            else { //스택이 비어있지 않고
                if(st.top() == '(' && s[j] == ')') { //top이 여는 괄호면서 다음 인자가 닫는 괄호면
                    st.pop();//Pop
                }
                else {//그 외의 경우는 모두 push
                    st.push(s[j]);
                }
            }
        }
        if(st.empty()) {
            cout << "YES" << "\n";
        }
        else {
            cout << "NO" << "\n";
        }
    }
}

---