[백준 2504번] 괄호의 값 풀이

#백준 #백준 2504번 #백준 괄호의 값

 

2504번: 괄호의 값

 

중첩되는 괄호에 대해 값을 저장하고 계산하는 문제이다. 괄호의 중첩은 스택을 이용하여 해결할 수 있다. 먼저, 입력된 문자열을 저장하고 스택을 생성한다.

string s;
cin >> s;

stack<string> st;

 

이후, 입력된 문자열의 각 자릿값을 판별하여 처리한다.

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

 

문자열의 자릿값이 ( 이고 닫는 괄호가 이어지지 않는 경우 스택에 문자열 "(" 을 저장한다.

 

 

//stack
(

 

문자열의 자릿값이 ( 이고 닫는 괄호가 이어지는 경우, 즉 () 인 경우 스택에 () 이 나타내는 값 "2"를 저장한다. 스택이 문자열을 저장하므로 2가 아닌 "2"를 저장해야 한다.

 

 

//stack
( 2

 

문자열의 자릿값이 [ 이고 닫는 괄호가 이어지지 않는 경우, 즉 단독 [ 인 경우 스택에 "[" 를 저장한다.

 

 

//stack
( 2 [

 

문자열의 자릿값이 [ 이고 닫는 괄호가 이어지는 경우, 즉 [] 인 경우 스택에 [] 이 나타내는 값 "3"을 저장한다.

 

 

//stack
( 2 [ 3

 

문자열의 자릿값이 닫는 괄호인 경우, 즉 ) 이거나 ] 일 경우 해당 괄호 단위에 저장된 숫자들을 모두 더해 숫자의 형태로 스택에 저장한다.

 

 

이전까지의 스택에서  ") 의 짝 ("  혹은  "] 의 짝 ["  이 나올 때까지 병렬로 저장된 숫자들을 모두 더한다. 이 케이스의 경우 ] 의 짝 [ 을 찾고, 해당 괄호 단위 안에 있는 숫자를 모두 더한 결과 3이 된다. [ ] 괄호로 쌓여있는 수는 x3배가 되므로 3 * 3 = 9 를 계산하여 스택에 덩어리로 넣는다.

 

//stack
( 2 9

 

이러한 과정을 반복하여 최종 스택을 도출한다.

 

//stack
22 

22 (

22 ( 3

// final stack
22 6

 

최종 스택에 숫자 외의 값이 포함 된 경우 올바른 괄호의 값이 아니었으므로 0을 출력하고 프로그램을 종료시킨다. 숫자들만 포함된 경우 숫자들을 모두 더해 정답을 구한다.

 

#include <iostream>
#include <cstdio>
#include <algorithm> 
#include <cstring>
#include <vector>
#include <cmath>
#include <tuple>
#include <stack>
using namespace std;

bool closeBracket(stack<string>& st, char bracket) {

    string open = (bracket == ']') ? "[" : "(";
    int mult = (bracket == ']') ? 3 : 2;

    int sum = 0;
    while (!st.empty() && st.top() != "(" && st.top() != "[") {
        sum+=stoi(st.top());
        st.pop();
    }

    if (st.empty() || st.top() != open) {
        printf("0");
        return false;
    }
    st.pop();
    st.push(to_string(sum*mult));
    return true ;
}

int getAnswer(stack<string> &st) {

    int re = 0;
    while (!st.empty()) {
        if (st.top() == "(" || st.top() == "[") return 0;
        re+=stoi(st.top());
        st.pop();
    }
    return re;
}

int main() {

    string s;
    cin >> s;

    stack<string> st;
    for (int i=0; i<s.size(); i++) {

        if (s.substr(i, 2) == "()") {
            st.push("2");
            i++;
        }
        else if (s.substr(i, 2) == "[]") {
            st.push("3");
            i++;
        }
        else if (s[i] == '(') st.push("(");
        else if (s[i] == '[') st.push("[");
        else if (s[i] == ']' || s[i] == ')')
            if (!closeBracket(st, s[i])) return 0;
    }
    printf("%d", getAnswer(st));
    return 0;
}