[BOJ] 9012 "괄호" 문제 풀이 & 소스 코드 with C/C++

#INFO

난이도 : SILVER4

알고리즘 유형 : STACK(스택)

∞ 문제 출처 : https://www.acmicpc.net/problem/9012

 

---

#SOLVE

VPS(괄호 문자열)이 성립하기 위해서는, 모든 여는 괄호와 닫는 괄호의 짝이 맞아야 한다.

(()() 문자열의 경우는, 첫 번째 여는 괄호의 닫는 괄호가 존재하지 않기에 VPS가 아니다.

(()()()) 문자열의 경우는, 모든 여는 괄호와 닫는 괄호의 짝이 존재하기에, VPS가 성립한다.

스택 자료구조를 이용해 문제를 풀이 하였는데, 여는 괄호만 스택에 넣는 방식을 채택하였다.

반복문을 이용해 문자열을 처음부터 끝까지 돌려서 여는 괄호를 만나면 push하고, 닫는 괄호를 만나면 여는 괄호 하나를 pop 한다. 반복이 모두 끝났을 때 스택이 비어있다면 VPS 문자열 이기에 YES를 스택이 비어있지 않다면 VPS 문자열이 아니기에 NO를 반환한다.

하지만 다음과 같은 상황도 생각해 주어야 한다. 스택은 모두 비어있지만, 닫는 괄호의 짝이 존재하지 않는 경우이다. 따라서, 스택이 빈 경우에만 여는 괄호를 pop하고 스택이 비었고, 닫는 괄호를 만난 경우라면 닫는 괄호의 짝이 존재하지 않는 상황이니 NO를 반환한다.

---

#CODE

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

string solution(string str) {
	stack<char> stk;
	for (char ch : str) {
		if (ch == '('){
			stk.push(ch);
		}
		else 
		{
			if(!stk.empty())
			{
				stk.pop();
			}
			else
			{
				return "NO";
			}
		}
	}
	
	if (stk.empty())
	{
		return "YES";
	}
	
	else
	{
		return "NO";
	}
}

int main()
{
	int testCase;
	cin >> testCase;	
	while(testCase--) {
		string str;
		cin >> str;
		cout << solution(str) << '\n';
	}
	return 0;
}

---