[C++] 백준 9012번 괄호

1. 문제이해

9012번: 괄호 (acmicpc.net)

9012번: 괄호

 

주어진 문자열을 입력받고, 해당 문자열이 VPS인지를 판단하는 알고리즘을 구현하는 것이 목표이다.

VPS 문자열이란, 괄호의 모양이 바르게 구성된 문자열로,

VPS 문자열이 맞으면 "YES", 아니면 "NO"를 출력해야한다.

 

 

 

2. 문제풀이

 

VPS 문자열인지를 판단하고 해당 결과에 맞게 출력해주면 되는 문자열이다.

VPS 문자열이란, 쉽게 말하자면 괄호의 쌍이 맞는 문자열이다.

아래 3가지의 예제를 통해 더 자세히 알아보자.

 

 

<예제 1>

( ) ( ( ) ) 의 경우,

열린 괄호 '(' 가 3개, 닫는 괄호 ')' 가 3개이며,

앞에서부터 차례로 쌍을 이루어 나가기 때문에 VPS 문자열이 맞다.

 

<예제 2>

( ) ) ( ) ( 의 경우,

열린 괄호  '(' 가 3개, 닫는 괄호 ')' 가 3개로 동일하지만,

괄호가 쌍을 이루지 않기 때문에 VPS 문자열이 아니다.

( 앞에서부터 열린괄호, 닫는 괄호, 닫는 괄호가 나오는데,

닫는 괄호가 2번 나오면, 두번째 닫는 괄호는 짝이 맞는 열린 괄호가 없기 때문에 쌍을 이루지 못하게 된다.

따라서, VPS 문자열이 아니다.)

 

<예제 3>

( ) ) ( ) 의 경우,

열린 괄호 '(' 가 2개, 닫는 괄호 ')' 가 3개로

짝이 맞지 않기 때문에 VPS 문자열이 아니게 된다.

 

 

즉, VPS 문자열인지 확인하기 위해서는

열린 괄호와 닫힌 괄호의 쌍이 맞는지, 개수가 맞는지를 확인하는 것이 중요하다.

닫힌 괄호가 나오면, 열린 괄호가 있는지 확인하고,

해당 열린 괄호와 닫힌 괄호는 제외해주는 식으로 나아가며 확인해주면 된다.

 

즉, 스택 자료구조를 이용해 위 방법을 구현하면 된다.

 

1. 스택을 통해 열린괄호 '(' 는 push,

 

2. 닫힌 괄호 ')' 는 스택에 열린 괄호가 있는지 확인 후

열린 괄호가 있다면, 해당 열린 괄호를 pop

열린 괄호가 없다면, 즉, 비어있다면 "NO"를 출력하면 된다.

(닫힌 괄호가 더 많은 경우, 닫힌 괄호가 맨 앞에 오는 경우 등)

 

3. 마지막까지 연산 후, 스택이 비어있지 않다면,

쌍이 맞지 않는 것이므로 "NO"를 출력한다.

(열린 괄호가 더 많은 경우 등)

 

 

 

3. 소스코드

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

int main() {	
	string bracket;  // 입력될 문자열
	int T;  // 입력 데이터의 수 
	int bracket_size = 0;  
	string result;
	
	cin >> T;
	for (int i = 0; i < T; i++) {
		stack<char> s;	// i가 달라질때마다 스택은 초기화되어야함
		result = "YES";	// result 값은 YES로 초기화

		cin >> bracket;	
		bracket_size = bracket.size();	

		// 문자열의 처음부터 탐색 시작
		for (int j = 0; j < bracket_size; j++) {
			if (bracket[j] == '(') {  // 여는 괄호일때
				s.push('(');
			}

			else if (bracket[j] == ')') {  // 닫는 괄호일때,
				if (!s.empty()) {  // 스택이 비어있지 않으면,
					s.pop();
				}
				else {  // 비어있으면
					result = "NO";
				}
			}
		}

		// 마지막까지 연산완료 후,
		// 여는 괄호와 닫는 괄호의 짝이 맞지 않는 경우	
		// 즉, 스택이 비어있지 않은 경우
		if (!s.empty()) {  
			result = "NO";
		}

		cout << result << endl;

	}

	return 0;
}

먼저, 테스트 할 문장의 개수(T)를 입력받는다.

for문안에 stack s를 정의하고, result 값을 "YES"로 두고,

문장의 길이를 bracket_size 변수값에 넣어준 뒤 문자열의 처음부터 탐색을 시작한다.

 

(for문 안에 위 2개의 변수를 정의한 이유는 다음과 같다.

1. stack은 for문의 i 값이 증감될때마다 매번 초기화되어야 하기때문.

초기화되지 않으면 이전 값이 중첩되어 올바른 결과가 나오지 못한다.

 

2. result값을 "YES"로 두고, 이어지는 for문에서 특정 경우에만 "NO"로 바뀌도록 했다.

만약, result 값 또한 for문 안에서 다시 초기화를 해주지 않게 되면,

이전 값과 중첩되어 올바른 결과가 나오지 않을 수 있게 된다. )

 

안쪽의 for문을 통해 문자열의 처음부터 탐색을 시작한다.

문자열을 탐색하면서, 열린 괄호 '(' 가 나오면, 그대로 스택에 push한다.

닫힌 괄호 ')' 가 나오면, 스택이 비어있는지 확인 후,

비어있지 않으면 pop, 비어있으면 result 값을 "NO"로 설정한다.

 

안쪽 for문의 과정을 모두 끝마친 이후, (해당 문자열을 검사한 이후)

스택에 문자가 남아있다면 열린괄호와 닫힌 괄호의 짝이 맞지 않았다는 것이므로,

result 값을 "NO"로 설정해준다.

 

위와 같은 과정을 반복하며, 각 테스트케이스에 대해

VPS 문자열인지를 판단한다.

 

 

---

너무 피곤한 수요일 아침이다..😴

목요일, 금요일만 잘 보내면 한주 푹 쉬니까, 조금만 더 화이팅해야지💪