[백준/BOJ][C++] 9012번 괄호

<문제 소개>

---

<소스 코드>

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

int main()
{
	// 쓰레드 환경이 아닐때 버퍼를 분리하여 처리속도를 빠르게 해줌
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T;
	cin >> T;
	
	vector<string> output;

	for (int i = 0; i < T; i++)
	{
		string s;
		cin >> s;

		stack<char> stk;
		bool isVPS = true;

		for (int j = 0; j < s.size(); j++)
		{
			char curWord = s[j];

			if (curWord == '(')
			{
				// '('인 경우 스택에 넣어줌
				stk.push(curWord);
			}
			else
			{
				// ')'인 경우
				// 지울 '(' 가 없는 경우 -> 반복문을 나감
				if (stk.empty())
				{
					isVPS = false;
					break;
				}

				// 마지막에 저장된 '(' 를 지움
				stk.pop();
			}
		}
		
		if (isVPS)
		{
			// for문을 다 돌고 나온 경우
			if (stk.empty())
			{
				// 스택이 비어있는 경우 -> 모든 괄호가 없어진 경우 -> VPS
				output.push_back("YES");
			}
			else
			{
				// 스택의 원소가 하나라도 있는 경우 -> VPS가 아님
				output.push_back("NO");
			}
		}
		else
		{
			// 지울 '(' 가 없어서 for문을 다 돌지 못하고 나온 경우 -> VPS가 아님
			output.push_back("NO");
		}
	}

	for (int i = 0; i < output.size(); i++)
	{
		cout << output[i] << "\n";
	}

	return 0;
}

---

<풀이과정>

1. T를 입력받고, 결과를 저장할 string형 벡터 output을 선언

2. T만큼 반복하며 입력 문자열 s를 입력받고 왼쪽괄호를 담을 스택 stk와 VPS인지를 판단할 isVPS를 선언한다.

3. 문자열 s의 각 원소를 돌면서 curWord에 저장하고, curWord가 '(' 인지 ')' 인지를 구분한다.

4. 왼쪽괄호 '(' 인 경우 스택 stk에 넣어준다.

5. 오른쪽 괄호 ')' 인 경우 스택에 있던 '(' 를 하나씩 지워줄 건데 만약 '(' 가 없다면 isVPS를 false로 바꾸고 그 즉시 반복문을 나와준다. 이외의 경우에는 pop을 이용해 마지막에 저장된 '(' 를 지워준다.

6. 반복문을 빠져나온 뒤 isVPS가 true이면 for문을 다 돌고 나온 경우인데, 이때 스택 stk가 비어있다면 모든 괄호가 짝지어 없어진 경우이므로 VPS이다. 따라서 output 벡터에 "YES"를 추가해준다.

7. 스택이 비어있지 않고 원소가 하나라도 남아있다면 짝이 없는 '(' 가 남아있는 것이므로 VPS가 아니다. 따라서 output 벡터에 "NO"를 추가해준다.

8. 이외에 아예 isVPS가 false인 경우에는 ')' 가 올바르지 않은 위치에 있어 반복문을 빠져나온 것이므로 VPS가 아닌 경우이다. 따라서 output에 "NO"를 추가해준다.

9. 이렇게 모든 입력에 대해 VPS 판단이 끝났다면 output 벡터를 돌면서 각 원소들을 줄마다 출력한다.

---

<코멘트>

처음엔 단순히 왼쪽과 오른쪽 괄호의 갯수가 같으면 되는 줄 알았는데 아니었다..ㅋㅋㅋ

오른쪽 괄호가 나왔을 때 왼쪽 괄호를 하나씩 지워주는 것이 키 포인트!

---

<제출결과>