9012 괄호 by C++

문제

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

 

해결한 방법

1. string으로 입력받아서 각 철자를 인덱싱해서 '('를 찾으면 left에 ')'를 찾으면 right에 1을 더한다.
2. 중간에 right가 left보다 커진다면 break후 NO출력
3. NO가 출력되지 않았다면 right와 left를 비교해서 같으면 YES 아니라면 NO 출력

#include <iostream> // cin, cout
#include <string> // string

int main()
{
	int t;
	cin >> t;
	cin.ignore();

	string buffer;
	int size = 0;
	while (t--){
		getline(cin, buffer);
		size = buffer.size();
		int left = 0, right = 0;
		int is_break = 0;
		for (int i = 0; i < size; i++){
			if (buffer[i] == '('){
				left++;
			}
			else {
				right++;
				if (right > left) {
					cout << "NO" << endl;
					is_break = 1;
					break;
				}
			}
		}
		if (is_break)
			continue;
		if (left == right)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
}

개선된 방법

right 와 left를 따로 두지 말고 stack이라는 한 변수로 더 효율적인 방법이 있음을 알게되습니다.

 

1. string으로 각 철자에 접근해 '('를 찾으면 stack++ ')'를 찾으면 stack--
2. 중간에 stack이 음수가 된다면 for문을 빠져나옴
3. stack이 0이라면 YES 출력 아니라면 NO출력

#include <iostream> // cin, cout, getline
#include <string> // string
using namespace std;

int main()
{
	int t;
	cin >> t;
	cin.ignore();

	string buffer;
	int size = 0;
	while (t--) {
		getline(cin, buffer);
		size = buffer.size();
		int stack = 0;
		for (int i = 0; i < size && stack >= 0; i++) {
			if (buffer[i] == '(') {
				stack++;
			}
			else {
				stack--;
			}
		}
		if (stack)
			cout << "NO" << endl;
		else
			cout << "YES" << endl;
	}
}

위 코드는 백준 C++ 기준 가장 빠른 답안인 tg314님의 코드를 참고했습니다.