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

문제 링크

9012번: 괄호

문제 요약

'('와 ')'로 이루어진 괄호 문자열이 주어질 때, 괄호의 모양이 바르게 구성된 올바른 괄호 문자열을 판정해야 한다.

접근 방법

이 문제의 알고리즘 분류는 스택으로 붙어 있지만 스택은 사용하지 않아도 됩니다.

괄호의 종류는 '(', ')' 뿐이기 때문에 스택에 저장해서 어떤 종류의 괄호가 대응될 차례인지 판정할 필요가 없습니다.

먼저 문자열을 입력 받습니다. 그리고 '('의 수를 저장할 변수를 하나 선언하고, '('가 나오면 1 증가시켜 줍니다. 그리고 만약에 ')'를 만나게 된다면 1 감소시켜 줍니다. 만약에 해당 변수의 값이 0인 상황에서 ')'를 만나는 경우에는 대응되는 '('가 없다는 것이기 때문에 올바른 괄호 문자열이 아니게 됩니다.

또한 문자열의 끝까지 검사를 완료했을 때, '('의 수를 저장하는 변수가 0이 아니라면 대응되는 ')'가 부족했다는 것이기 때문에 올바른 괄호 문자열이 아니게 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

void func(void)
{
	string str;
	cin >> str;

	int cnt = 0;
	for (auto& i : str)
	{
		if (i == '(')
			cnt++;
		else
		{
			if (!cnt)
			{
				cout << "NO\n";
				return;
			}
			else
				cnt--;
		}
	}

	cout << (!cnt ? "YES\n" : "NO\n");
}

int main(void)
{
	int t;
	cin >> t;
	
	while (t--)
		func();

	return 0;
}