[BaekJoon/C#] 2504. 괄호의 값

 

문제 

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.

1. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 
2. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. 
3. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.

예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다. 

1. ‘()’ 인 괄호열의 값은 2이다.
2. ‘[]’ 인 괄호열의 값은 3이다.
3. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
4. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.

여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다. 

 

입력

첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.

 

출력 

첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다. 

 

예제1

입력:

(()[[]])([])

출력: 

28

 

예제2

입력:

[][]((])

출력: 

0

 

 

코드

using System; 
using System.Text; 
using System.Collections.Generic; 

class Program 
{ 
    static void Main(string[] args) 
    { 
        List<char> bracket = new List<char>();
        List<string> prefix = new List<string>();
        List<int> productIndex = new List<int>();
        string str = Console.ReadLine();
        bool VPS = true;
        
        if(!str[0].Equals('(') && !str[0].Equals('[')) VPS = false;
        else 
        {
            bracket.Add(str[0]);
            prefix.Add(str[0].Equals('(') ? "2" : "3");
            
            for(int i=1; i<str.Length; i++) 
            { 
                if(!VPS) break;
                if(str[i].Equals('(') || str[i].Equals('['))
                {
                    int index = prefix.Count<2||bracket.Count==0 ? 0 : prefix.Count-1;

                    if(str[i-1].Equals('(') || str[i-1].Equals('[')) 
                    {
                        prefix.Insert(index, "*");
                        productIndex.Add(index+2);
                    }
                    else 
                    {
                        if(bracket.Count==0) prefix.Insert(0, "+");
                        else prefix.Insert(productIndex[bracket.Count-1], "+");
                    }
                    bracket.Add(str[i]);
                    prefix.Add(str[i].Equals('(') ? "2" : "3");
                }
                else if(str[i].Equals(')') || str[i].Equals(']'))
                {
                    if(bracket.Count==0) VPS = false;
                    else if(str[i].Equals(')'))
                    {
                        if(bracket[bracket.Count-1].Equals('(')) 
                        {
                            bracket.RemoveAt(bracket.Count-1);
                            if(str[i-1].Equals(')') || str[i-1].Equals(']')) productIndex.RemoveAt(productIndex.Count-1);
                        }
                        else VPS = false;
                    }
                    else if(str[i].Equals(']'))
                    {
                        if(bracket[bracket.Count-1].Equals('[')) 
                        {
                            bracket.RemoveAt(bracket.Count-1);
                            if(str[i-1].Equals(')') || str[i-1].Equals(']')) productIndex.RemoveAt(productIndex.Count-1);
                        }
                        else VPS = false;
                    }
                    if(bracket.Count==0) productIndex.Clear();
                }
                else VPS = false;
            }     
        }

        if(!VPS) Console.WriteLine("0"); 
        else if(bracket.Count>0) Console.WriteLine("0");
        else Console.WriteLine(calc(prefix.ToArray()));
    } 
    
    static string calc(string[] prefix)
    {
        List<string> stack = new List<string>();
        
        for(int i=0; i<prefix.Length; i++)
        {
            stack.Add(prefix[i]);
            int num1;
            int num2;
                
            while(stack.Count>2 && Int32.TryParse(stack[stack.Count-1], out num1) && Int32.TryParse(stack[stack.Count-2], out num2))
            {
                string operators = stack[stack.Count-3];
                stack.RemoveRange(stack.Count-3, 3);
                        
                switch(operators)
                {
                    case "+":
                        stack.Add((num1+num2).ToString());
                        break;
                    case "*":
                        stack.Add((num1*num2).ToString());
                        break;
                }
            }
        }
        return stack[0];
    }
}

참고

정답률이 28%인 이유가 있었다.

정답일거라고 생각했는데 예상치 못한 테스트 케이스에서 실패하고 수정하고 실패하고 수정하고..

코드가 다소 깔끔하지 못한 것 같아서 추후에 수정해보려고 한다. 

 

((()[])[])
답 26

(()[()]()[()])
답 32

(()[()]()[()])(()[()]()[()])
답 64

[](()[()]()[()])(()[()]()[()])
답 67

[](()[()]()[()])()(()[()]()[()])
답 69

[](()[()]()[()])()(()[()]()[()])[]
답 72

((()[()]()[()])()(()[()]()[()])[])
답 138

 

내가 적용했던 테스트 케이스들이고, 아래는 출처 링크다.

https://www.acmicpc.net/board/view/62519