[ 백준 2504 ] 괄호의 값 (C++)

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

2504번: 괄호의 값

 

개인적으로 너무 어려운 문제였다. 하루 꼬박 고민하다가 그냥 다른 사람의 풀이를 봤다. 알고리즘은 아래와 같다. 입력값의 인덱스 0번째 문자부터 순차적으로 진행된다.

 

초기화 : tmp = 1, result = 0, impossible = false
입력값 : input

1. input[i] ='(', 스택에 push, tmp *= 2
2. input[i] = '[', 스택에 push, tmp *= 3
-> 여는 괄호가 나오면 무조건 스택에 push하고 tmp에 값 곱해준다

3. input[i] = ')'
----- stack.top() != '(' || stack.empty(), impossible = true, break
4. input[i] = ']'
----- stack.top() != '[' || stack.empty(), impossible = true, break
-> 닫는 괄호가 나왔는데 스택의 top이 같은 종류의 여는 괄호가 아니거나 스택이 비어있다면 이상한 식이므로 멈춘다

5. input[i] = ')'
----- input[i - 1] = '(', result += tmp
----- tmp /= 2, stack.pop()
6. input[i] = ']'
----- input[i - 1] = '[', result += tmp
----- tmp /= 3, stack.pop()
-> 닫는 괄호가 나왔는데 바로 이전 값이 같은 종류의 여는 괄호면 result에 tmp 더해준다
   tmp에 값 나눠주고, 스택 pop은 항상 고정

 

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

int main(){
    string input;
    int tmp = 1, result = 0;
    bool impossible = false;
    stack<char> s;
    
    cin >> input;
    
    for(int i = 0; i < input.size(); i++){
        // 1,2. 여는 괄호가 나오면 무조건 스택에 push하고 tmp에 값 곱해준다
        if(input[i] == '('){
            tmp *= 2;
            s.push('(');
        }
        else if(input[i] == '['){
            tmp *= 3;
            s.push('[');
        }
        
        // 3,4. 닫는 괄호가 나왔는데 스택의 top이 같은 종류의 여는 괄호가 아니거나 스택이 비어있다면 
        //      이상한 식이므로 멈춘다
        // 5,6. 닫는 괄호가 나왔는데 바로 이전 값이 같은 종류의 여는 괄호면 result에 tmp 더해준다
        //      tmp에 값 나눠주고, 스택 pop은 항상 고정
        else if (input[i] == ')' ){
            if(s.empty() || s.top() != '('){
                 impossible = true;
                 break;
            }
            else if (input[i - 1] == '(')
                result += tmp;
            s.pop();
            tmp /= 2;
         }

        else if (input[i] == ']'){
            if(s.empty() || s.top() != '['){
                impossible = true;
                break;
            }
            else if (input[i - 1] == '[')
                result += tmp;
            s.pop();
            tmp /= 3;
        }
    }
    
    if(impossible || !s.empty())
        cout << 0 << endl;
    else
        cout << result << endl;
    
    return 0;
}