백준 9012 괄호 [C]

문제

https://www.acmicpc.net/problem/9012

9012번: 괄호

 

풀이

올바른 괄호 문자열 (VPS) 인지는 어떻게 알 수 있을까에 대해 고민해보자.

1. 여는 괄호 ( 일때는 PUSH, 닫는 괄호 ) 일때는 POP을 하여 문자열 입력이 끝났을 때, 스택에 아무것도 남아 있지 않는다면 올바른 괄호 문자열이고, 반대로 남아있다면 올바른 괄호문자열이 아닌 것이다.

2. 또한 중간에 POP을 하지 못하는 경우가 발생하는 경우에는 올바르지 않은 괄호 문자열이다.

위 두가지만 판별해주면 쉽게 풀이할 수 있을 것으로 보인다. 

 

그런데, 이 문제에서는 괄호가 한가지이다. PUSH 할경우 '(' 만 넣을 수 있고 다른 문자같은경우를 고려할 필요가 없다. 그렇다면 굳이 스택을 사용해야 할까? 스택 역할을 하는 변수 한개만으로도 충분하다. 

 

코드

#include<stdio.h>
#include<string.h>
int T,len;
char str[100],stack[100];
int main()
{
  int i;
  scanf("%d\n",&T);
  for(int tt=0;tt<T;tt++){
    scanf("%s",str);
    int top=0;
    len=(int)strlen(str);
    for(i=0;i<len;i++){
      if(str[i]=='('){
        top++;
      }
      else{
        top--;
        if(top<0) break;
      }
    }
    if(i==len && top==0) printf("YES\n");
    else printf("NO\n");
  }
  return 0;
}