greentea31's Note

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

풀이 과정

(, ), [, ]로 이루어진 문자열을 보고, 올바른 괄호 문자열인지 판단하고, 맞으면 문제의 조건에 맞게 괄호의 값을 출력하는 문제이다.

올바른 괄호 문자열 판단 자체는 )가 들어오면 스택탑이 (, ]가 들어오면 스택탑이 [인지 판단만 해주면 되는데 괄호의 값을 계산하기가 조금 까다롭다. 

(,나 [가 나오면 정답에 더해질 변수를 (초기값 1)을 문제의 조건에 맞게 2나 3을 곱해주고, )나 ]가 나오면 스택이 아닌 문자열에서 바로 앞에 있는 문자가 뭐였는지에 따라 변수를 정답에 더하고 변수를 나눌지, 아니면 그냥 변수를 나눌지 판단해주어야 한다.

예제로 주어진 문자열에서 정답에 더해질 변수 mul과 정답 변수 ans의 변화는 위의 그림과 같은데, 밑의 문제를 풀기 위한 아이디어와 동일한 아이디어를 사용해 괄호의 값을 구하게 된다.

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

올바른 괄호 문자열 판단의 아이디어, 쇠막대기 문제의 아이디어를 모두 활용해야 하는 문제였다.

소스 코드

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    stack<char> st;
    string s;
    cin >> s;

    int ans = 0;
    int mul = 1;

    for (int i = 0; i <= s.length(); i++) {
        if (s[i] == '(') {
            mul *= 2;
            st.push('(');
        } else if (s[i] == '[') {
            mul *= 3;
            st.push('[');
        } else if (s[i] == ']') {
            if (st.empty() || st.top() != '[') {
                cout << 0;
                return 0;
            }

            if (s[i-1] == '[') ans += mul;
            st.pop();
            mul /= 3;
        } else if (s[i] == ')') {
            if (st.empty() || st.top() != '(') {
                cout << 0;
                return 0;
            }

            if (s[i-1] == '(') ans += mul;
            st.pop();
            mul /= 2;
        }
    }

    if (st.empty()) cout << ans;
    else cout << 0;

    return 0;
}