알고스팟 - 짝이 맞지 않는 괄호 (BRACKETS2) [C++]

이 문제는 스택을 이용해서 간단하게 풀 수 있다. 문자열의 길이가 최대 10,000 이므로 테스트케이스까지 고려했을 때 O(n^2) 알고리즘은 사용할 수 없다. 스택을 이용하면 한번의 순회만으로 가능하므로 O(n) 시간이 소요되어 1초를 넘기지 않는다.

 

 

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

using namespace std;

bool correct(char left, char right) {
	if (left == '(' && right == ')') {
		return true;
	}
	if (left == '{' && right == '}') {
		return true;
	}
	if (left == '[' && right == ']') {
		return true;
	}
	return false;
}

bool solve(string &input) {
	stack<char> st;

	for (char c : input) {
		if (c == '(' || c == '[' || c == '{') {
			st.push(c);

			continue;
		}

		if (st.empty()) {
			return false;
		}

		if (!correct(st.top(), c)) {
			return false;
		}

		st.pop();
	}

	if (!st.empty()) {
		return false;
	}

	return true;
}

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

	int C;

	cin >> C;

	for (int test = 0; test < C; test++) {
		string input;

		cin >> input;

		bool answer = solve(input);

		if (answer) {
			cout << "YES" << '\n';
			continue;
		}

		cout << "NO" << '\n';
	}

	return 0;
}