괄호의 값 — 곱셈 누적 + 스택 (BOJ 2504)

아이디어

• 스택엔 마커만 넣음: (→-1, [→-2

• 진행 중 곱(temp) 유지:

  • ( 만나면 temp *= 2, [ 만나면 temp *= 3
  • 바로 닫히는 ()·[]를 만나면 현재 temp를 ans에 더함
  • 닫을 때는 해당 배수를 나누고(pop), 불일치면 실패 처리

구현 포인트

• 문자·숫자 혼용 X → int 스택 + 마커로 통일
• 닫는 괄호 처리 분기: )는 -1, ]는 -2와만 매칭
• 중간에 규칙 위반 시 ans = 0 후 종료
• 끝나고 스택 비어있지 않으면 0

복잡도

• 한 번 순회 O(n), 스택 O(n)

코드 (통과)

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int ans = 0;
    stack<int> st;
    string str;
    int temp = 1;

    cin >> str;
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == '(') {
            st.push(-1);
            temp *= 2;
        }
        else if (str[i] == '[') {
            st.push(-2);
            temp *= 3;
        }
        else if (str[i] == ')') {
            if (st.empty() || st.top() != -1) {
                ans = 0;
                break;
            }
            if(str[i - 1] == '(') {
                ans += temp;
                temp /= 2;
                st.pop();
            }
            else {
                temp /= 2;
                st.pop();
            }
        }
        else if (str[i] == ']') {
            if (st.empty() || st.top() != -2) {
                ans = 0;
                break;
            }
            if(str[i - 1] == '[') {
                ans += temp;
                temp /= 3;
                st.pop();
            }
            else {
                temp /= 3;
                st.pop();
            }
        }
    }
    if (!st.empty()) ans = 0;
    cout << ans;
    return 0;
}

체크

• 시작이 )나 ]면 즉시 0 처리
• 중첩 ([])처럼 곱 누적이 잘 더해지는지
• 모든 괄호 처리 후 스택 비었는지 확인