백준 #2504 - 괄호의 값

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

2504번: 괄호의 값

스택으로 분류된 2504 괄호의 값 문제 입니다.

 

 

using System;
using System.Collections.Generic;
using System.Linq;
 
namespace _2504
{
    public class Solution
    {
        public const int SMALL = 2;
        public const int LARGE = 3;
 
        public string input;
 
        public Solution(string input) => this.input = input;
 
        public bool IsRight()
        {
            var stack = new Stack<char>();
 
            foreach(char c in this.input)
            {
                switch (c)
                {
                    case '(':
                    case '[':
                        stack.Push(c);
                        break;
 
                    case ')':
                        if (!(stack.Count == 0) && stack.Peek() == '(') stack.Pop();
                        else return false;
                        break;
 
                    case ']':
                        if (!(stack.Count == 0) && stack.Peek() == '[') stack.Pop();
                        else return false;
                        break;
                }
            }
            return (stack.Count == 0) ? true : false;
        }
 
        public int Calculation()
        {
            var strStack = new Stack<string>();
 
            foreach(char c in input)
            {
                if (c == '(' || c == '[') strStack.Push(c.ToString());
 
                else if(c == ')')
                {
                    int temp = 0;
                    while(strStack.Peek() != "(")
                    {
                        temp += int.Parse(strStack.Pop());
                    }
                    strStack.Pop();
                    strStack.Push((temp == 0) ? SMALL.ToString() : (temp * SMALL).ToString());
 
                    //출력.
                    var list = strStack.ToList();
                    list.Reverse();
                    list.ForEach(x => Console.Write(x + " "));
                    Console.WriteLine();
                }
 
                else if (c == ']')
                {
                    int temp = 0;
                    while (strStack.Peek() != "[")
                    {
                        temp += int.Parse(strStack.Pop());
                    }
                    strStack.Pop();
                    strStack.Push((temp == 0) ? LARGE.ToString() : (temp * LARGE).ToString());
 
                    //출력
                    var list = strStack.ToList();
                    list.Reverse();
                    list.ForEach(x => Console.Write(x + " "));
                    Console.WriteLine();
                }
            }
 
            int result = 0;
            while (strStack.Count != 0)
                result += int.Parse(strStack.Pop());
            return result;
        }
    }
 
    class Program
    {
        static void Main(string[] args)
        {
            var solution = new Solution(Console.ReadLine());
            Console.WriteLine(solution.IsRight()? solution.Calculation() : 0);
        }
    }
}
 

이번 문제는 주제가 주제인 만큼 스택으로 풀었습니다.

비슷한 문제를 풀어본적이 있었는데 재귀로 풀었던 기억이 있습니다.

 

설명 들어가겠습니다.

 

Solution 클래스를 만들었습니다.

string Input => 괄호 문자열을 받았습니다.

bool IsRight() => 괄호 문자열이 올바른 괄호쌍들을 이루고 있는지 확인합니다.

int Calculation() => 괄호 문자열의 값을 구합니다.

 

() 괄호의 경우 2의 값을 가지고 있어 상수로 선언했습니다.

[] 괄호 또한 3의 값을 상수로 선언했습니다.

 

 

1. bool IsRight()

먼저 괄호 문자를 처음부터 읽어가며 집어넣을 스택을 하나 선언했습니다.

 

간만에 switch문 한번 써봤습니다. 여는 괄호를 만난다면 스택에 바로 집어넣습니다.

")" => 를 만나면 직전에 여는 괄호가 "(" 인지 확인하고 맞다면 쌍이 이루어졌으므로 Pop() 합니다.

"]" => 마찬가지 입니다. "["를 가장 마지막에 만났는지 확인하고 Pop()합니다.

 

처음부터 끝까지 문자열을 확인한 후에 스택이 비어있다면 true, 아니라면 false를 리턴합니다.

 

ex) ((([][]) 이런 경우가 있을 수 있습니다. 대괄호 두개는 제대로 인식하겠지만 소괄호의 경우

제대로 쌍이 이루어지지 않아 스택에 남아있을 겁니다. 이를 위해 마지막에 확인해줍니다.

 

 

2. int Calculation()

계산 함수 입니다. 마찬가지로 스택을 사용했으며 제너릭으로 string 타입으로 했습니다.

중간중간 괄호 쌍이 이루어졌다면 그 괄호쌍을 값으로 대체할 겁니다.

 

중간 계산 결과를 출력하게 해봤습니다.

계산 결과를 보면 닫는 괄호를 만났을 때 괄호 안까지의 계산 결과를 연산하고 연산한 결과를 다시 스택에 집어넣는것으로 알고리즘을 짰습니다.

 

계산을 하기 전 괄호열이 맞는지 미리 확인했기 때문에 맞는 괄호열만 계산 했습니다.

 

그 방법은

1. 여는 괄호를 만나면 스택에 집어넣는다.

2. 닫는 괄호를 만나면 해당 여는 괄호를 만날 때까지 넣어놓은 숫자를 스택에서 뽑아 계산합니다.

3. 숫자가 없었다면 괄호쌍에 해당하는 값을 넣고 있었다면 연산한 결과를 스택에 넣습니다.

4. 마지막으로 스택에 쌓인 계산 결과들을 모두 더해 리턴합니다.

 

계산 과정 출력을 보시면 충분히 이해하실거라 생각합니다.

 

포스팅 마치겠습니다.