[백준 9012] 괄호

문제 링크 : https://www.acmicpc.net/problem/9012

9012번: 괄호

올바른 괄호 쌍 문자열을 하나 보자

 

( ( ) ( ) ) ( ( ( ) ) )

 

VPS일 경우에 앞에 등장하는 작은 괄호쌍부터 하나씩 제거해 나갈 수 있다.

 

( ( ) ( ) ) ( ( ( ) ) )

 

( ( ) ) ( ( ( ) ) )

 

( ) ( ( ( ) ) )

 

( ( ( ) ) )

 

( ( ) )

 

( )

 

빨간색 괄호쌍은 제거되는 괄호쌍이다

 

---

사실 맨 처음 괄호문자열에서 바로 눈에 들어오는 가장 작은 괄호쌍 세개를 한번에 정리할 수도 있었다

 

( ( ) ( ) ) ( ( ( ) ) )

 

( ) ( ( ) )

 

그러나 이러한 방법으로 괄호들을 제거해 나갈경우 누가봐도 구현하기 복잡하며 시간도 오래걸린다

 

따라서 앞에서부터 순서대로 괄호들을 보며 괄호쌍을 제거할 수 있는 방법이 필요하다

 

다시 맨 처음에 했던 방법을 반복해보자

 

( ( ) ( ) ) ( ( ( ) ) )

 

앞에서부터 보기 시작해서 아직 닫히지 않은 열린 괄호들에 대한 정보를 저장하는 스택을 하나 만들자

 

초록색은 스택에 들어가 있는 열린 괄호이다

 

( ( ) ( ) ) ( ( ( ) ) )

 

1, 2 괄호까지 봤을 때 스택에는 열린 괄호가 두개 들어가 있다

 

스택에 있는 두 괄호는 모두 아직 닫히지 않았다는 것을 유의하자

 

( ( ) ( ) ) ( ( ( ) ) )

 

( ( ) ) ( ( ( ) ) )

 

3번쨰 괄호는 닫히는 괄호이다

 

이 괄호는 당연하게도 스택의 가장 위에 있는 열린 괄호와 쌍을 이루어 나간다

 

따라서 스택에 있는 열린 괄호는 하나로 줄어들고

 

쌍을 이룬 괄호는 삭제된다고 볼 수 있다.

 

( ( ) ) ( ( ( ) ) )

 

새로운 열린괄호는 스택에 추가해준다

 

스택에 열린괄호가 두개 들어있다

 

( ( ) ) ( ( ( ) ) )

 

( ) ( ( ( ) ) )

 

다음으로 등장한 닫히는 괄호가 앞에 있던 열린괄호와 쌍을 이루어 제거되었다

 

스택에 열린괄호는 한개가 되었다

 

( ) ( ( ( ) ) )

 

( ( ( ) ) )

 

이번에 들어온 닫힌 괄호는 맨 처음에 등장한 열린 괄호와 쌍을 이루어 제거되었다

 

스택에 모든 열린 괄호가 쌍을 이루어 스택이 비게 되었다

 

다른 괄호들도 마찬가지의 과정으로 전부 제거될 수 있다

---

( ( ) ( ) )

 

위의 괄호문자열에서 알 수 있듯이

 

맨 처음 열린 괄호와 쌍을 이루는 닫힌 괄호 사이에는

 

스택에 들어갔다가 제거되는 괄호쌍들만 존재한다

 

따라서 마지막에 닫힌 괄호가 등장했을 때

 

스택에 존재하는 괄호는 맨 처음 열린 괄호가 유일하다

 

대충 이런 느낌으로 스택을 이용해서 올바른 문자열을 처리할 수 있다

---

그러나 중요한 것은 VPS인지 아닌지 확인하는 것이다

 

이는 스택을 이용해서 VPS를 처리하는 과정에서 확인할 수 있다

 

 

1. 닫힌괄호에 대응되는 열린괄호가 앞에 없는 경우 (스택에 없는 경우)

 

ex) ( ) )

 

이런 경우에는 마지막 닫힌 괄호가 나왔을 때 스택에서 제거될 열린 괄호가 없으므로 진행에 문제가 생긴다

 

 

2. 마지막까지 쌍을 이루는 닫힌 괄호를 못 찾은 열린 괄호

 

ex) ( ( )

 

이런 경우 마지막까지 모든 괄호쌍을 제거하여도 스택에 열린 괄호가 존재한다

---

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

int main(void) {
	int n;
	scanf("%d", &n);

	string str;
	for (int i = 0; i < n; i++) {
		cin >> str;    //입력
		int cnt = 0;    //stack의 size
		for (int i = 0; i < str.size(); i++) {
			if (str[i] == '(') {   
				cnt++;    //여는 괄호 ( 일 경우에 stack에 여는 괄호를 push
			}
			else {    //닫히는 괄호 )
				if (cnt == 0) {    //쌍을 맞출 수 있는 여는 괄호가 앞에 없었음
					cnt++;    //잘못된 괄호쌍 
                    //(마지막에 cnt가 0이 아니면 no를 출력하므로 그냥 cnt++해서 break)
					break;    //더 볼 필요 없음
				}
				cnt--;    //앞에 나온 열린괄호 하나랑 쌍을 이루어서 stack에서 pop
			}
		}
		if (cnt != 0)printf("NO\n");    //다 했는데 비어있지 않으면 여는 괄호가 너무 많은거
		else printf("YES\n");

	}

	return 0;
}