[알고리즘문제] 백준 9012 괄호

https://www.acmicpc.net/problem/9012

9012번: 괄호

 

괄호가 정상적인 괄호 문자열인지 검증하는 문제

정상적인 괄호라면 "YES"출력

아니라면 "NO" 출력

#include<iostream>
#include<vector>
#include<stack>

using namespace std;

bool confirm(string object) {
	if (!object.size()) return true;
	if (object.size() % 2) return false;
	if (object[0] == ')') return false;
	if (object[object.size() - 1] == '(') return false;

	stack<char> s;
	s.push(object[0]);
	for (int i = 1; i < object.size(); i++) {
		if (s.size() && s.top() == '(' && object[i] == ')') s.pop();
		else s.push(object[i]);
	}
	if (s.size()) return false;

	return true;
}

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

	vector<string> v;

	int N = 0;
	cin >> N;

	for (int i = 0; i < N; i++) {
		string basket = "";
		cin >> basket;
		v.push_back(basket);
	}


	for (int i = 0; i < N; i++) {
		bool con = confirm(v[i]);
		if (con)
			cout << "YES" << "\n";
		else
			cout << "NO" << "\n";
	}

	return 0;
}

stack을 쓰면 간단하게 풀린다.

stack에 마지막에 쌓은 괄호가 여는 괄호이고 현재 가리키는 괄호가 닫는 괄호이면 stack의 top를 제거하며 대상 문자열을 모두 순회한 후 stack에 남아있는 괄호가 있다면 정상적인 괄호가 아니다.

 

Time complexity : O(N*M) 문자열의 갯수 * 문자열의 길이

Space complexity : O(N*M) 문자열의 갯수 * 문자열의 길이