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

www.acmicpc.net/problem/2504

2504번: 괄호의 값

stack 자료구조를 이용해 여러 가지의 경우로 올바른 괄호인지를 판별하고 값을 계산하는 문제였습니다.

 

풀이방법

 1. 열린괄호가 나오면 해당 값을 무조건 곱해줍니다.

 2. 중간에 짝이 안맞는다면 올바르지 못한 괄호열이므로 break해줍니다.

 3. 닫힌괄호가 나온다면 (()) [[]]식으로 겹친 괄호인지 판단하기 위해 바로 이전 괄호 문자열을 확인해줍니다. 만약 바로 이전 괄호와 짝이 맞는 문자라면 여태 계산한 값을 결과값에 더해줍니다. 그 후 괄호의 값에 맞춰 나누어줍니다.

 

Code

#include <bits/stdc++.h>
using namespace std;

string brackets; 
stack <char> st;
int ans, piv = 1, valid = 1;

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

Test Case

 

][]

답 3

(()[])

답 10

((()[]))

답 20

((()[]))[]

답 23

((()[])[])

답 26

()[()]

답 8

(()[[]])

답 22

(()[[]])[]

답 25

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

답 78

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

답 16

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

답 32

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

답 64

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

답 67

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

답 69

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

답 72

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

답 138