백준 9012번: 괄호

 

풀이

 열린 괄호 '(' 가 닫힌 괄호 ')' 와 한 쌍이 되면 YES, 그렇지 않다면 NO를 출력하는 전형적인 스택 문제이다. 문자열의 괄호를 관리할 스택 자료구조를 먼저 만들었다.

 

 이제 입력받은 문자열에 for 문을 돌려보자.

1. '('를 만나면 스택에 '('를 넣는다.

2. ')'를 만나면 '('와 한 쌍을 만들어주기 위해 스택에서 '('를 꺼낸다.

   2-1. 스택이 비어있다면 ')'와 한 쌍을 이루는 '('가 없다는 뜻이기 때문에 "NO"를 출력한다.

3. for 문이 끝났는데 스택이 비어있지 않다면 '('가 남는다는 뜻이기 때문에 "NO"를 출력한다. 

 

코드

#include <iostream>
#include <stack>

using namespace std;

int T;

void init() {
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(false);
}

int main() {
	init();

	cin >> T;

	for (int i = 0; i < T; i++) {
		string s;
		bool answer = true;
		stack<char> st;

		cin >> s;
		for (int j = 0; j < s.size(); j++) {
			if (s.at(j) == '(')	st.push(s.at(j));
			if (s.at(j) == ')') {
				if (st.empty()) {
					answer = false;
					break;
				}
				else {
					st.pop();
				}
			}
		}

		if (answer && st.empty()) cout << "YES" << "\n";
		else cout << "NO" << "\n";
	}
}