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

 

알고리즘 분류: 자료 구조, 문자열, 스택

문제 링크: https://www.acmicpc.net/problem/9012

9012번: 괄호

 

 

 

【 문제 】

 

괄호 문자열(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"를 한 줄에 하나씩 차례대로 출력해야 한다.

 

 

【 풀이 】

 

C++의 string 클래스와 스택 자료구조를 이용하여 풀었다.

 

이 문제의 핵심은 '(' 와 ')' 서로 개수가 맞아떨어져야 한다는 점이다.

이 말은 즉, 여는 괄호 '('의 개수만큼 닫는 괄호 ')'가 나와야 하는 것이다.

한 쌍의 괄호 문자열만이 VPS로 인정받는지라 "())(()" 처럼 "(X)" 형태의 내용물에 특히 주의해야 한다.

즉 문자열이 끝나기 전에 '(' 보다 ')'가 더 많이 나오는 형태면 NO를 출력하게 해야 한다.

 

string 클래스를 이용하여 괄호 문자열을 입력받은 다음, 문자열의 인덱스를 검사해 가며

시인성이 좋게 '(' 자체를 스택에 저장해 가며 코드를 구성했다.

그리고 ')' 이 나올 때마다 스택에 저장된 '(' 를 추출해 내고

반복문에서 나왔을 때 검사가 정상적으로 이루어지고, 스택이 모두 비어있을 때 YES를 출력하게 구현했다.

 

 

【 코드 】

 

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

int main(void)
{
	int i,j;
	int t;
	cin >> t;
	for (i = 0; i < t; i++)
	{
		string vps;
		stack<char>ps;
		cin >> vps;
        
		for (j = 0; j < vps.size(); j++)	
		{
			if (vps.at(j) == '(')
				ps.push('(');
			else
			{
				if (ps.empty())		
					break;
				ps.pop();
			}
		}
        
		if (j == vps.size()&&ps.empty())		//	문자열의 검사가 정상적으로 이루어지고 스택도 비어있을 때
			cout << "YES\n";
		else
			cout << "NO\n";
            
	}
	return 0;
}