C# 9012번 괄호

문제

코드 :

using System;
using System.Collections;
namespace _3
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = Convert.ToInt32(Console.ReadLine());
            for (int i = 0; i < N; i++)
            {
                string PS = Console.ReadLine();
                Stack stack = new Stack();
                for (int j  = 0; j < PS.Length; j++)
                {
                    //맨 초기값
                    if (stack.Count == 0)
                        stack.Push(PS[j]);
                    else
                    {
                        //"()" 모양이 만들어질때마다 pop시켜서
                        //stack이 올바른 괄호 문자열이라면 모두 pop될것이고
                        //아니라면 몇개가 남을것이다.
                        if (stack.Peek().ToString() == "(" && PS[j] == ')')
                        {
                            stack.Pop();
                        }
                        else
                            stack.Push(PS[j]);
                    }
                }
                Console.WriteLine(stack.Count == 0 ? "YES" : "NO");
            }
           
        }
    }
}

문제 풀이 :

처음에는 단순히 '('의 갯수와 ')'의 갯수가 같기만 하면 될거라 생각했으나 )(와 같은 경우는 성립되지 않는다는 것을 알게 되고 '올바른 괄호 문자열 (VPS)' 을 체크하는게 중요하다는 것을 알게 되었다. 

만약 ( ( ) ( ) ) 와 같은 문자열이 들어온다면  작은 VPS 두개를 큰 VPS로 감싼 형태임을 알 수 있다. 문자열 전체가 VPS인지를 확인하기 위해 VPS일때마다 무언가 체크했음 했다. 그래서 VPS가 완성될때마다 해당 VPS를 제거해주고 모든 문자열이 다 제거된다면 문자열 전체가 VPS고 문자열이 하나라도 남아있다면 VPS가 아닐것이라고 생각했다.

( ( ) ( ) ) 의 경우 스택의 흐름은 이렇게 된다.

1. (

2. ( (

3. ( ( ) <--- VPS가 완성됐으므로 Pop 

   (

4. ( (

5. ( ( ) <--- VPS가 완성됐으므로 Pop 

   (

6. ( ) <--- VPS가 완성됐으므로 Pop

7. null

이런식으로 모든 문자열을 스택에서 Pop에 성공한다면 'YES'를 출력하고 아니면 'NO'를 출력하도록 했다.