[백준] 9012번 - 괄호 / C++

문제

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

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

 

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다. 

 

출력

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다. 

 

코드

#include <iostream>
#include <string>

using namespace std;

bool isVPS(string &ps)
{
	int i, cnt = 0;

	for (i = 0; i < ps.size(); i++)
	{
		if (ps[i] == '(')
			cnt++;
		else
			cnt--;
		if (cnt < 0)
			return false;
	}
	if (cnt != 0)
		return false;
	return true;
}

int main()
{
	int t, T;
	string ps;

	cin >> T;
	for (t = 0; t < T; t++)
	{
		cin >> ps;
		if (isVPS(ps))
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
	return 0;
}

 

스택을 사용하는 문제이지만 cnt 변수만을 사용해 해결했다. cnt 변수는 스택을 사용하는 경우 스택의 크기라고 생각할 수 있다. '('인 경우 push() 하고, ')'인 경우 pop() 하는 것처럼 cnt를 증감해준다. 만약 cnt가 음수가 된다면 열린 괄호가 없는데 괄호를 닫는 것, 즉 스택이 비어있는데 pop()을 하는 것이므로 유효하지 않다. 또한 모든 문자열을 읽은 후 cnt가 0이 아니라면 열린 괄호가 있는데 괄호를 닫지 않은 것, 즉 스택에 값이 남아있는 것이므로 VPS가 아니다.

 

링크

9012번: 괄호

inbdni/Baekjoon