[문제풀이] 백준 2504 - 괄호의 값

📢 문제

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

📢 알고리즘

구현, 스택

📢 풀이

#include <iostream>
#include <string>
#include <stack>

using namespace std;

int main()
{
  string input;
  cin >> input;

  stack<int> s;
  int result = 0;

  for (int i = 0; i < input.size(); i++)
  {
    char now = input[i];
    if (now == '(')
    {
      s.push(-1);
    }
    else if (now == '[')
    {
      s.push(-2);
    }
    else if (now == ')' || now == ']')
    {
      bool isTwin = false; // 현재의 닫힌 괄호가 처리됐는지
      // 스택 체크
      int sum = 0;
      while (!s.empty())
      {
        int top = s.top();
        s.pop();
        if (top == -1 || top == -2)
        {                              // 스택에서 여는 괄호를 만난 경우
          if (top == -1 && now == ')') //(),(x)
          {
            if (sum == 0) //()
            {
              sum = 2;
            }
            else //(x)
            {
              sum = 2 * sum;
            }
            s.push(sum);
            isTwin = true;
          }
          else if (top == -2 && now == ']') //[],[x]
          {
            if (sum == 0) //[]
            {
              sum = 3;
            }
            else //[x]
            {
              sum = 3 * sum;
            }
            s.push(sum);
            isTwin = true;
          }
          else
          { // 괄호 짝이 안맞는 경우
            cout << 0;
            isTwin = false;
            exit(0);
          }
          break;
        }
        else
        { // 스택에서 숫자를 만난 경우
          sum += top;
        }
      }
      if (!isTwin)
      { // 닫힌 괄호가 많은 경우
        cout << 0;
        exit(0);
      }
    }
  }

  while (!s.empty())
  {
    int top = s.top();
    if (top == -1 || top == -2) // 열린 괄호가 많은 경우
    {
      cout << 0;
      exit(0);
    }
    result += top;
    s.pop();
  }
  cout << result;
}

• ( : 스택에 -1 넣음, [ : 스택에 -2 넣음

• 올바르지 않은 경우

  1. 닫힌 괄호가 많은 경우 ex. (x))
     • 이것 때문에 계속 90%에서 틀렸음...
     • 그런데 테스트 케이스 돌려보면 제대로 나왔음. 테케 문제 없어도 내가 처리 안한 경우 다시 확인해보자..
     • 스택이 비었는데 닫힌 괄호 처리를 아직 못한 경우
  2. 열린 괄호가 많은 경우 ex. ((x)
  3. 괄호 개수는 맞지만, 괄호 순서가 안 맞는 경우 ex. ([x)]

• 닫힌 괄호를 만나는 순간 값을 계산해서 스택에 넣음

  • 스택에서 열린 괄호(-1 or -2)를 만날 때까지 pop
  • 열린 괄호가 아닌 수를 만나는 경우 sum에 더함 : xy=x+y 처리
  • 열린 괄호를 만났을 때 sum=0인 경우 sum=2 or sum=3으로 바꿔주기, 스택에 push : ()=2, []=3 처리
  • 열린 괄호를 만났을 때 sum>0인 경우 sum*=2 or sum*=3, 스택에 push : (x)=2x, [x]=3x 처리