[BOJ] 괄호의 값 2504번 C++

 

문제

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.

1. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.
2. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다.
3. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.

예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다.

1. ‘()’ 인 괄호열의 값은 2이다.
2. ‘[]’ 인 괄호열의 값은 3이다.
3. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
4. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.

여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다.

입력

첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.

출력

첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다.

 

접근 방식

 

만약 중첩된 괄호가 있다면 이를 파악해서 곱해주는 것이 이 문제의 핵심이다

따라서, 이를 파악하기 위해 어떤 방식을 사용해야 할지 고민이 많았다..

처음 생각했던 방식은 char 자료형을 가지는 stack에 만약 () 이런 괄호가 있다면 '2' 문자를 넣고, [] 괄호라면 '3'문자를 넣는 방식으로 시도하였다

하지만 매번 계산할 때마다 int 형을 char 형으로 바꾸고, stack에 다시 넣어줄 때는 char형에서 int 형으로 다시 바꿔야 하는 불편함이 생겼다.

 

따라서, 새롭게 찾은 방식은 시작 중괄호라면 ( = -2값을, 시작 대괄호라면 [ = -3의 값을 스택에 넣어주어 계산이 훨씬 용이하게 바뀌었다.

 

생각보다 복잡하지는 않지만 코드가 굉장히 길어지고 생각할 경우의 수가 많은 문제였다

 

 

 

코드

 

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

string str;
stack<int> st;

int main() {
    cin >> str;
    for (auto c : str) {
        if (c == '(') {
            st.push(-2); 
        } else if (c == '[') {
            st.push(-3); 
        } else if (c == ')') {
            int n = 0;
            while (!st.empty() && st.top() != -2) {
                if (st.top() < 0) { 
                    cout << 0 << endl;
                    return 0;
                }
                n += st.top();
                st.pop();
            }
            if (st.empty() || st.top() != -2) {
                cout << 0 << endl;
                return 0;
            }
            st.pop();  
            st.push(n == 0 ? 2 : 2 * n);  
        } else if (c == ']') {
            int n = 0;
            while (!st.empty() && st.top() != -3) {
                if (st.top() < 0) { 
                    cout << 0 << endl;
                    return 0;
                }
                n += st.top();
                st.pop();
            }
            if (st.empty() || st.top() != -3) {
                cout << 0 << endl;
                return 0;
            }
            st.pop();  
            st.push(n == 0 ? 3 : 3 * n);  
        }
    }

    int ans = 0;
    while (!st.empty()) {
        if (st.top() < 0) {
            cout << 0 << endl;
            return 0;
        }
        ans += st.top();
        st.pop();
    }

    cout << ans << endl;
    return 0;
}