백준 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”를 한 줄에 하나씩 차례대로 출력해야 한다.  

 

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

int main(void)
{
	int num;
	string text;
	cin >> num;

	for (int i = 0; i < num; i++)
	{
		stack<char> sign;
		int sum = 0;
		cin >> text;
		for (auto e : text)
		{
			if (e == '(')
			{
				sign.push(-1);
			}
			else
			{
				sign.push(1);
			}
		}
		int flag = 0;
		while (!sign.empty())
		{
			sum += sign.top();
			if (sum < 0)
			{
				cout << "NO" << endl;
				flag = 1;
				break;
			}
			sign.pop();
		}

		if (flag == 1)
			continue;

		if (sum == 0)
		{
			cout << "YES" << endl;
		}

		else
		{
			cout << "NO" << endl;
		}
	}

	return 0;
}

이전에 과에서 알고리즘 스터디 할 때 한 번 코드 리뷰를 했었던 문제이다. 너무 오래 전에 풀었던 문제라 사실상 처음부터 다시 푸는 느낌이었다. 이 문제는 스택에 대해서 공부를 하고, 스택 라이브러리를 다루고나서 처음 접하기에 매우 좋은 문제라고 생각된다. 문제 난이도도 그렇게 어렵지 않고 스택의 구조를 머리 속으로 그려가면서 스택에 대해 숙지할 수 있다고 본다.

 

이 문제는 괄호가 형성되는 것을 어떻게 처리할 것이냐의 문제이다. 처음에는 단순하게 '(' 기호가 들어오면 1, ')' 기호가 들어오면 -1로 처리해서 합해서 0이 되면 괄호가 하나 생성되게끔 코드를 짰었다. 하지만 문제에서는 우리가 생각하는 '()' 이렇게 닫힌 괄호를 원하지, ')(' 반대로 열린 괄호를 원하지 않는다. 그래서 나는 반복문을 통해 우리가 원하는 괄호 규칙에 어긋나는게 확인되었을 경우 바로 'NO'를 출력하게끔 코드를 짰다.

int flag = 0;
while (!sign.empty())
{
	sum += sign.top();
	if (sum < 0)
	{
		cout << "NO" << endl;
		flag = 1;
		break;
	}
	sign.pop();
}

if (flag == 1)
	continue;

이 반복문이 괄호 예외처리를 잡아내는 핵심 코드이다. 일단 while 반복문을 스택이 텅텅 빌 때까지 돌린다. 여기서 끝에 있는 괄호부터 하나씩 꺼내 검사를 한다. 만약 괄호가 닫히지 않았거나, 앞으로의 코드에서 괄호가 닫히지 않음을 감지하면 그대로 반복문을 탈출시켜 'NO'를 출력시키게끔 한다. 그래서 '(' 기호를 넣을 때는 1이 아닌 -1로 정하고 탈출 조건을 괄호 누적값이 0 미만일 경우로 잡는다.

 

여기서 while문을 탈출시키는 방법에서 좀 고민을 했었는데, goto문을 사용 하느냐 마느냐였다. 생각나는게 goto문 밖에 없어서 쓰려고 했었으나 찾아보니 코드에서처럼 flag로 탈출시키는 방법이 있어서 flag를 썼다. 프로그래밍 이론을 공부하다보면 워낙 goto문에 민감한 사례들이 많이 나와서 가능하면 이런 짤막한 코드에도 goto문을 지양하기로 했다. flag를 통해 탈출 했으면 다른 조건문은 검사하지 않고 다음 입력을 읽어들인다.

 

if (sum == 0)
{
	cout << "YES" << endl;
}

else
{
	cout << "NO" << endl;
}

위의 while 반복문을 코드 리뷰를 보다보면 이런 의문이 들 것이다. '())'가 입력되면 양수가 되어서 조건문에 걸리지 않는 것이 아닌가? 그래서 뒤에 조건문을 더 적었다. 앞서 sum이 음수가 되어 탈출하는 경우는 continue로 해당 케이스를 'NO'로 출력하게 만들고 다음 케이스를 받아들인다. 그렇지 않은 경우 저렇게 0이 아닌 양의 값이 나오면 뒤의 if-else문을 통해 'NO'를 출력하게 만든다. 완벽하게 문제의 의도대로 괄호가 닫히려면 '(' 기호와 ')' 기호의 개수가 같을 수 밖에 없으며 이 말은 sum 값이 무조건 0이 나온다는 뜻이다.