[BOJ/백준][Silver1] 2504 : 괄호의 값 (C++)

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

2504번: 괄호의 값

 

[난이도] Silver1
[유형] 스택

[풀이]
실버1치고 발상이 어려워서 다른 분들의 풀이를 참고했습니다.
(()[[]]) = 2 * (2+3*3) = 2*2 + 2*3*3 이 되는 분배법칙을 이용합니다.
cur 변수를 1로 초기화 해놓고
- 여는 괄호 ( 가 나오면 2를 [가 나오면 3을 곱해줍니다.
- 닫는 괄호가 나오면 해당 괄호가 cur에 미치는 영향은 끝났으므로 2 또는 3으로 나눠줍니다.
  예를 들어, (()[[]]) = 2 * (2+3*3) 에서 두번 째 첫 번째 ) 가 나왔을 때, cur은 2*2에서 2*2/2 가 되어 다시 2가 됩니다.
  그래야, 3*3에 2만 곱해줄 수 있기 때문입니다.
- () 혹은 [] 모양의 인접한 올바른 문자열이라면 2*2 + 2*3*3 에서 한 덩어리의 값이 끝남을 의미하므로 나누기 전에 cur의 값을 total에 더해 줍니다.
- 중간중간 올바른 문자열이 아닌 경우를 체크하여 0을 return 해줍니다.
- 모든 문자열을 순회하고도 stack에 값이 남아있다면 올바른 문자열이 아니므로 0을 return 해줍니다.

 

#include <cstdio>
#include <stack>
#include <string>
#include <iostream>
using namespace std;
string s;
int sol(){
    stack<char> st;
    int total=0,cur=1;
    for(int i=0;i<s.size();i++){
        if(s[i]=='('){
            cur*=2;
            st.push(s[i]);
        }else if(s[i]=='['){
            cur*=3;
            st.push(s[i]);
        }else{
            if(st.empty()) return 0;
            if(s[i]==')') {
                if(st.top()!='(') return 0;
            }else{
                if(st.top()!='[') return 0;
            }
            st.pop();
            if(s[i-1]=='('||s[i-1]=='[') total+=cur;
            if(s[i]==')') {
                cur/=2;
            }else{
                cur/=3;
            }
        }
    }
    if(!st.empty()) return 0;
    return total;
}
int main(){
    cin >> s;
    cout << sol();
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver1/2504.cpp