(C++) 백준 2504번 - 괄호의 값

문제 링크 : https://www.acmicpc.net/problem/2504

2504번: 괄호의 값

풀이

스택을 이용하여 풀이를 진행하면 된다. 올바른 입력인지 확인하는 것은 이전에도 풀어보았기 때문에 어렵지 않으나, 값들을 곱해주는 것이 무척 어려웠다.

더하는 것은 단순히 이전에 나온 것이 짝이 맞는 괄호인지만 확인하면 돼서 어렵지 않았는데, 곱해주는 것은 고민해 봐도 도저히 생각이 나지 않아서 다른 사람의 풀이를 참고하였다.

열린 괄호가 입력되었을 때 곱해주는 아이디어가 중요한 포인트이다.

#include <iostream>
#include <stack>

using namespace std;

stack<char> S;
int result;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);  
    
    string str;
    bool valid = true;
    cin >> str;

    int add = 1; // 곱해줄 값
    for(int i = 0; i < str.size(); i++){
        if(str[i] == '('){
            S.push(str[i]);
            add *= 2; // 소괄호는 곱해줄 값 2배 증가
        }    
        else if(str[i] == '['){
            S.push(str[i]);
            add *= 3; // 대괄호는 곱해줄 값 2배 증가
        }else if(str[i] == ')'){
            if(!S.empty() and S.top() == '('){ // 올바른 입력
                // 직전에 나온 괄호가 짝이 맞는 여는 괄호면 전체 결과에 더해주기
                if(str[i-1] == '(') result += add;
                S.pop();
                add /= 2; // 소괄호가 닫혔으므로 2로 나눠줌
            }else { // 올바르지 않은 입력
                valid = false; 
                break;
            }
        }else if(str[i] == ']'){
            if(!S.empty() and S.top() == '['){ // 올바른 입력 
                // 직전에 나온 괄호가 짝이 맞는 여는 괄호면 전체 결과에 더해주기
                if(str[i-1] == '[') result += add;
                S.pop();
                add /= 3; // 대괄호가 닫혔으므로 3으로 나눠줌
            }else { // 올바르지 않은 입력
                valid = false; 
                break;
            }
        }
    }
    if(valid and S.empty()) cout << result; // 스택에 괄호들이 남아있으면 올바른 입력이 아님
    else cout << 0;
}