알고리즘 ] 백준 9012번 - 괄호

괄호 검사

- 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.

 

 

[풀이]

- Stack을 활용하여 마지막에 넣은 데이터를 참고하여 풀 수 있다.

 

1) 여는 괄호'(', '[' 가 나오는 경우에는 Stack에 Push를 해준다.

2) 닫히는 괄호 ')', ']'가 나올 때는 해당 Stack에 마지막에 저장된 괄호와 쌍이 같은지 확인하고 같으면 stack에서 하나를 pop해주고 틀리다면 이 문제는 틀린 것으로 보고 NO를 출력해준다.

3) 마지막까지 확인하고 Stack 저장공간이 비어있다면 YES 그렇지 않다면 NO를 출력해준다.

 

[결과]

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

using namespace std;
int main()
{

	int cnt;
	cin >> cnt;

	for (int recIdx = 0; recIdx < cnt; recIdx++)
	{
		stack<char> st;
		string input;
		cin >> input;

		bool result = true;
		for (auto ch : input)
		{
			if (ch == '(' || ch == '[')
			{
				st.push(ch);
			}
			else
			{
				if (!st.empty() && st.top() == '(' && ch == ')')
				{
					st.pop();
				}
				else if (!st.empty() && st.top() == '[' && ch == ']')
				{
					st.pop();
				}
				else
				{
					result = false;
					break;
				}
			}
		}
		if (st.empty() && result)
		{
			cout << "YES" << endl;
		}
		else
		{
			cout << "NO" << endl;
		}
	}
	return 0;
}