백준 알고리즘 9012번: 괄호 [C++]

문제 출처: www.acmicpc.net/problem/9012

9012번: 괄호

1. 코드

#include <iostream>
#include <string>
#include <stack>

using namespace std;

int main(void)
{
	int t;
	cin >> t;
	while (t--)
	{
		string arr;
		stack <char> s;
		bool flag = false;
		cin >> arr;

		for (char c : arr)
		{
			if (c == '(') s.push('(');
			else if (s.empty())
			{
				flag = true;
				cout << "NO" << endl;
				break;
			}
			else s.pop();
		}
		if (!flag)
		{
			if (s.empty()) cout << "YES" << endl;
			else cout << "NO" << endl;
		}
	}
	return 0;
}

(실행)

2. 풀이

이 문제는 스택을 이용해서 푸는데 '(' 입력할 때 스택에 push를 해주고, ')'를 입력하게 되면 pop을 해주어 최종적으로 스택에 남아있는게 있다면 올바른 괄호이고, 그렇지않다면 올바르지않은 괄호이기 때문에 스택을 이용하여 쉽게 해결할 수 있다.

for (char c : arr)
{
	if (c == '(') s.push('(');
	else if (s.empty())
	{
		flag = true;
		cout << "NO" << endl;
		break;
	}
	else s.pop();
}

먼저 문자열을 순차적으로 접근할 때 '('가 입력되어있다면 스택에 push해준다. 그런데 만약 스택이 비어있는 상황에는 올바르지 않은 괄호이기 때문에 NO를 출력한다. 이 두 경우에 해당하지않으면 스택에 pop을 해준다.

if (!flag)
{
	if (s.empty()) cout << "YES" << endl;
	else cout << "NO" << endl;
}

이미 NO를 출력했다면 넘어가고 그렇지않고, 스택이 비어있다면 올바른 괄호이기 때문에 YES를 출력하고 그렇지않다면 NO를 출력한다.

3. 느낀 점

출력할 때 Yes, No로 출력을 해서 계속 틀렸는데 다음부터는 문제를 잘 읽어봐야겠다.