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

링크 - https://www.acmicpc.net/problem/2504

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 이다.

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

---

<아이디어>

• 문자를 정수로 변환하여 스택에 삽입하고 삭제한다.
• 여는 괄호 (, [ 는 스택에 항상 push 한다.
• num 스택의 역할은 연산해야 할 숫자를 저장하는 것이다.
• op 스택은 괄호(입력값)를 저장한다.
• op 스택은 여는 괄호와 닫는 괄호가 짝이 맞을 경우 pop 연산을 진행한다.
• num 스택은 괄호 안의 값을 누적하여 연산한다.

코드가 길지만 따라가다 보면 굉장히 직관적이라는 것을 알 수 있다. (선생님께서 설명해주신 코드인데 이해하기 정말 좋은 것 같다.)

---

<소스코드>

#include <bits/stdc++.h>
using namespace std;
#define MAX 35
char inp[MAX];
int t, f;
int ret, tmp;
stack<int>num, op;
int convert(char c)
{ 
   if(c == '(') return -2;
   else if(c=='[') return -3;
   else if(c==')') return 2;
   else return 3;
}
int main()
{     
    scanf("%s", inp);
    f = 1;
    for(int i=0;inp[i]!='\0' and f;i++)
    {   
        t = convert(inp[i]); // 여는 괄호( num은 숫자 / op는 괄호 )
        if(t < 0)
        {   
           num.push(t);
           op.push(t);
        }
        else
        { // 잘못된 괄호인 경우
           if(op.empty() or t*(-1) != op.top()) f = 0;
           else
            { // 괄호 빼기
              op.pop();
              // 괄호 안에 있는 값 계산
              tmp = 0;
              while(num.top() != t*(-1))
              {   
                 tmp += num.top();
                 num.pop();
              }
              num.pop(); // 괄호 안의 총 값 스택에 저장
              if(tmp == 0) num.push(t);
              else num.push(tmp*t);
            }
        }
    }
    if(!op.empty()or!f) printf("0");
    else
    {   
        while(!num.empty())
        {   
           ret += num.top();
           num.pop();
        }
        printf("%d", ret);
    }
}