[STACK] BOJ 9012 번 문제풀이

문제분석

 

굉장히 읽기 싫을 정도로 긴 문제지만

결국 소괄호가 한쌍으로 존재하는 가? 

를 묻는 문제네요. ㅎㅎ

 

알고리즘 문제를 풀 때, 접근법이 굉장히 중요한 게

제가 처음에 이 문제를 접근하는 

방법은 이렇습니다.

 

'(' , ')' 두 개의 개수를 카운트해서

같으면 VPS 이다 ~ 

 

라고 접근했습니다.

이 방법 역시 그렇게 어렵진 않지만

굉장히 단순 무식한 방법 같았습니다.

 

그래서 다른 분들의 코드를 보니

세상에 천재들이 많더군요.

 

개발자 지망생 김 모 씨의 접근법은 이렇습니다.

 

여는 괄호 '(' 가 나오면 무조건 스택에 PUSH 하고

닫는 괄호 ')' 가 나왔을 때,

배열 안에 여는 괄호 '(' 가 존재하면 스택에서 POP 하고

배열이 비어있다면 FALSE  하는 겁니다.

 

같은 문제를 이렇게 구현할 수 있다는 점에서 

정말 놀랐습니다.... 

 

어쨌든 이 문제는 이런 식으로 

한 줄 한줄 문자열을 받아서

해당 문자열이 VPS 인지 판별한 후 

YES or NO 를 출력하는 문제였습니다.

 

 

코드

 

#include "bits/stdc++.h"

using namespace std;

bool compare(string str)
{
	int len = (int)str.length();
	stack<char> arr;

	for (int i = 0; i < len; i++)
	{
		char c = str[i];

		if (c == '(') arr.push(str[i]);
		else
		{
			if (!arr.empty()) arr.pop();	
			else return false;
		}
	}
	return arr.empty();
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	string str;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> str;
		if (compare(str)) cout << "YES" << '\n';
		else cout << "NO" << '\n';
	}
	return 0;
}