BOJ - 괄호 9012

 

해결방법

스택을 사용한 문제이다.

구조는 다음과 같다.

(을 만나면 스택을 추가. )을 만나면 스택의 top을 제거.

만약 스택이 없는데 )을 만나는 경우 flag를 설정하고 루프를 끝내버린다.

 

만약 스택이 비어있지 않거나 flag가 올라가 있다면 잘못된 경우이므로 NO가 출력되고 그렇지 않다면 YES가 출력되는 구조이다.

 

정답 코드

#include <iostream>
#include <stack>

using namespace std;

int main()
{
	int TestCase, count = 0, flag = 0;
	string PS;

	cin >> TestCase;

	for (int i = 0; i < TestCase; i++)
	{
		stack<char> stack;
		cin >> PS;
		
		for (int j = 0; j < PS.size(); j++)
		{
			if (PS[j] == '(')
			{
				stack.push(PS[j]);
			}
			else if (PS[j] == ')')
			{
				if (stack.empty())
				{
					flag = 1;
					break;
				}
				else
				{
					stack.pop();
				}
			}
		}

		if (!stack.empty() || flag == 1)
		{
			cout << "NO" << endl;
		}
		else
		{
			cout << "YES" << endl;
		}

		flag = 0;
	}

	return 0;
}