(BOJ) 2504 풀이

#include <bits/stdc++.h>
using namespace std;

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    string input;
    cin >> input;
    stack<char> S;
    int flag = 0, ans = 0, tmp = 1;
    for (int i = 0; i < input.size(); i++)
    {
        if (input[i] == '(')
        {
            tmp *= 2;
            S.push(input[i]);
        }
        if (input[i] == '[')
        {
            tmp *= 3;
            S.push(input[i]);
        }
        if (input[i] == ')')
        {
            if (input[i - 1] == '(') // 2
            {
                S.pop();
                ans += tmp;
            }
            else if (!S.empty() && S.top() == '(')
            {
                S.pop();
            }
            else
            {
                flag = 1;
                break;
            }
            tmp /= 2;
        }
        else if (input[i] == ']')
        {
            if (input[i - 1] == '[') // 3
            {
                S.pop();
                ans += tmp;
            }
            else if (!S.empty() && S.top() == '[')
            {
                S.pop();
            }
            else
            {
                flag = 1;
                break;
            }
            tmp /= 3;
        }
    }
    if (!S.empty())
    {
        flag = 1;
    }
    if (!flag)
        cout << ans;
    else
        cout << 0;
}

이해하는데에 조금 걸린 문제였다.

[] → 3

() → 2

[x] → x*3

(x) → x*2

(x,y,z) → x+y+z

(값)(값) → 값+값

위 규칙을 이용해서 괄호값을 계산해야한다.

여는 괄호가 나타날 때마다 tmp에 2 or 3 을 곱한 뒤,

닫는 괄호가 나타났을 때, 직전 괄호와 쌍이 맞으면 ans 에 더해줬다.

이후 tmp 를 2 or 3 으로 나눈다.

직전 괄호와 쌍이 안맞고, 스택에 있는 괄호와도 안맞으면 잘못된 괄호이므로 flag 변수를 1로 세팅하고 종료.

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

위와 같은 예시가 있을 때,

(() : 일단 여기까지 진행했을 때 tmp 변수는 4고, 이 값을 ans 에 저장한 후, 소괄호를 빠져나왔으니 tmp 를 2로 나눈다.

올바른 괄호라면, 안쪽에 뭐가 있든 일단 이 괄호의 최솟값은 4가 된다. (()).

[[]]) : 현재 tmp 가 2 이므로, 2*3*3 이 ans 에 더해진다. 2가 곱해진 이유는, 대괄호 두 쌍이 소괄호 안에 있기 때문이다.

위 계산형식은, (2+6) → (2+6) * 2 가 아니라 2*2 + 6*2 이다.

더한 뒤 2를 곱하는게 아니라 괄호값을 미리 곱한뒤 ans 에서 더해진다. ( 곱셈 분배법칙 )

2*2+3*3*2+3*2 이런느낌으로