(c++)백준 9012번: 괄호

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

9012번: 괄호

 

[풀이]

두 가지 방법을 통해 풀어보았다.

1. int형 변수를 사용하여 '('가 나오면 +1, ')'가 나오면 -1 하는 방법

2. stack을 사용하여 '('가 나오면 push 1, ')'가 나오면 pop 하는 방법

 

※공통적으로 주의할 점

-맨 처음에 ')'가 나오거나 맨 뒤에 '('가 나오는 경우는 무조건 "NO"

-')'와 짝을 이루는 '('가 앞에 없는 경우 "NO" 출력하고 끝내기

 

1. int형 변수 사용한 코드

#include <iostream>
#include <string>
using namespace std;

int T;
string str;

void solution() {
	cin >> T;
	while (T--) {
		int vps = 0 ;//0이면 VPS임
		cin >> str;
		bool Break = false;//')'짝이 앞에 없으면 true
		
		//맨 앞에 ')'이 오거나 맨 뒤에 '('이 오면 NO
		if (str[0] == ')' || str[str.size() - 1] == '(') {
			cout << "NO" << endl;
			continue;
		}

		for (int i = 0; i < str.size(); i++) {
			if (str[i] == '(')
				vps++;
			else if (str[i] == ')')
				vps--;

			//')'짝이 앞에 없으면 NO
			if (vps < 0) {
				cout << "NO" << endl;
				Break = true;
				break;
			}
		}
		if (Break)
			continue;

		if (vps == 0)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
}

int main() {
	solution();
	return 0;
}

 

2. stack 사용한 코드

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int T;
string str;

void solution() {
	cin >> T;
	while (T--) {
		cin >> str;
		stack<int>s;//'('이면 1 push, ')'이면 pop
		bool Break = false;//')'앞에 짝이 되는 '('가 없으면 true

		for (int i = 0; i < str.size(); i++) {
			if (str[i] == '(')
				s.push(1);
			else if (str[i] == ')') {
				//앞에 짝이 되는 '('가 없으면
				if (s.empty()) {
					cout << "NO" << endl;
					Break = true;
					break;
				}
				//앞에 짝이 되는 '('가 있으면
				else {
					s.pop();
				}
			}
		}
		if (Break)
			continue;

		//짝이 되는 ')'를 갖지 못하는 '('가 있으면
		if (!s.empty()) {
			cout << "NO" << endl;
		}
		//모두 짝을 이루면
		else if (s.empty()) {
			cout << "YES" << endl;
		}
	}
}

int main() {
	solution();
	return 0;
}