[BOJ] 2504 : 괄호의 값

2504 : 괄호의 값

풀이

스택

스택을 활용해야한다는것은 바로 눈치챘지만,

혼자 손으로 풀어봐도 어떤식으로 해야 값을 분배법칙처럼 계산할 수 있을까 오래 고민했다.

스택에 추가할때 값을 2혹은 3씩 곱하고, pop할때 2혹은 3씩 나누는 계산을 하면 된다.

키포인트는 문제에 쓰여있는 ‘([)]’는 올바른 괄호열이 아니라는것.

즉 반드시 () 혹은 [] 가 나오게된다.

그때 지금까지 곱했던 값을 sum변수에 추가해주면 된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
#include <stack>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string a;
    cin >> a;
    stack<char> s1;
    stack<char> s2;
    int sum = 0;
    int cur = 1;
    int flag = 0;
    for (int j = 0; j < a.size(); j++) {
        if (a[j] == ')') {
            if (s1.empty()) {
                flag = 1;
                break;
            }
            cur /= 2;
            s1.pop();
        }
        else if (a[j] == ']') {
            if (s2.empty()) {
                flag = 1;
                break;
            }
            s2.pop();
            cur /= 3;
        }
        else if(a[j]=='('){
            if (j < a.size() - 1 && a[j + 1] == ')') {
                sum += cur * 2;
                j++;
            }
            else {
                cur *= 2;
                s1.push(a[j]);
            }
        }
        else if(a[j]=='['){
            if (j < a.size() - 1 && a[j + 1] == ']') {
                sum += cur * 3;
                j++;
            }
            else {
                cur *= 3;
                s2.push(a[j]);
            }
        }
    }
    if (flag || !s1.empty() || !s2.empty()) {
        cout << 0;
    }
    else {
        cout << sum;
    }

    
    return 0;
}
Written on March 17, 2019