괄호(9012)

괄호(9012)

2019, Jun 02    
  • https://www.acmicpc.net/problem/9012
  • 이 문제는 stack구조를 이용하여 문제를 해결하는 유명한 문제 입니다.
  • 만약 여는 괄호 ‘(‘가 이벽으로 들어오면 스택에 쌓습니다.
  • 만약 닫는 괄호가 들어오면 케이스가 나뉘게 됩니다.
    • 먼저 스택에 여는 괄호가 하나도 쌓여있지 않다면 닫는 괄호와 짝을 이룰 수 없습니다. 즉 잘못된 괄호 쌍입니다.
    • 만약 스택의 마지막이 여는 괄호라면 이번에 들어온 닫는 괄호와 짝을 이룰 수 있습니다. 이 때 스택의 마지막 여는 괄호를 pop 해줍니다.
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;	
	
	while (N--) {

		string s;
		vector<char> v;
		cin >> s;
		int ans = true;
		for (int i = 0; i < s.size(); ++i) {
		    // 만약 여는 괄호 '('가 이벽으로 들어오면 스택에 쌓습니다.
			if (s[i] == '(') {
				v.push_back('(');
			}
			else if (s[i] == ')') {
                // 먼저 스택에 여는 괄호가 하나도 쌓여있지 않다면 
                // 닫는 괄호와 짝을 이룰 수 없습니다. 즉 잘못된 괄호 쌍입니다.
				if(v.empty()){
					ans = false;
					continue;
				}
				//만약 스택의 마지막이 여는 괄호라면 이번에 들어온 닫는 괄호와 짝을 이룰 수 있습니다. 
				// 이 때 스택의 마지막 여는 괄호를 pop 해줍니다.
				else if(v.back() == '(') {
					v.pop_back();
				}
			}
		}

		if (!v.empty()) {
			ans = false;
		}

		if (ans) {
			cout << "YES" << '\n';
		}
		else {
			cout << "NO" << '\n';
		}
	}
}