[c++] 백준 2504 : 괄호의 값

[c++] 백준 2504 : 괄호의 값

 

난이도 🥈실버1

 

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

2504번: 괄호의 값

---

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

접근1

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



(()[[]]) -> 2*(2 + (3*3)) = 22

()와 []의 값은 분리되어 값이 증가해야 했고, 각각의 값을 더하기도 해야했기 때문에

그냥 눈에 보이는 2*(2 + (3*3)) 이런 방식을 구현하기는 어려웠다.



분배법칙을 적용해서 식을 다시 정리해보니 (2*2) + (2*3*3) = 22가 되었다.

(() 이것이 2*2가 되려면 괄호가 시작될 때 특정 변수에 2를 곱하다가 괄호가 닫힐 때 그 결과를

정답으로 출력할 변수에 더해주는  방식을 생각해보았다.



1. 입력값을 반복문으로 순회하다가 '('가 나타나면 스택에 '('를 추가하고 특정 변수에 2를 곱한다. (초기값 1)

2. ')'가 나타날 때, 앞의 값이 '('라면 ()이므로 변수에 모인 값을 정답으로 출력할 변수에 더해준다.

3. 스택의 top에 있던 값 '('를 pop으로 뺀다.



이렇게 하면 소괄호와 대괄호 뭉치가 여러개 있더라도 곱해져 있는 각각의 값을 서로 더해서 정답으로 출력할 변수에 담을 수 있었다.



그러나 이 방식을 그대로 적용하자니 [[]]의 경우에는 문제가 발생했다.

아까 분배법칙을 적용했기 때문에 여기서는 3*3이 아니라 2*3*3으로 계산되어야 했다.

스택에 '('가 남아있긴 했으나 이 값을 활용해서 2*3*3을 계산하기가 쉽지 않아 다른 방법을 고안해 보았다.



처음에 문자열이 (()까지 읽히면 pop으로 빼내는 코드로 인해 스택에는 (만 남게 된다.

곱의 결과를 담고 있던 변수에는 2*2가 남아 있고, 그 값을 정답 변수에 할당해 주었었다.



스택에 '('가 남아 있는 것처럼, 이 변수에도 2만 남아 있는 상태에서 [[]]의 3*3의 값이 그대로 곱해진다면

2*3*3을 구현할 수 있었다!

그리고 그 값을 다시 정답변수에 더해주면 (2*2) + (2*3*3) = 22라는 값을 얻어낼 수 있었다.





여기서 중요한 것은, 괄호를 닫는다고 무조건 정답변수에 값을 더해주면 안된다는 점이었다.

(()[[]]) -> 여기서 분배법칙을 활용해 외부의 2를 각각의 항에 곱해주었기 때문에 맨 마지막에 있는 ')'가 나오더라도

추가적으로 정답변수에 값을 더하면 안되었기 때문이다.

그럼 결국 괄호가 닫힐 때 그 앞의 값이 열린 괄호가 아닌 경우에는 정답변수에 값을 더해주지 않도록 조치를 취해야 했다.

접근2

올바르지 못한 괄호열은 다음과 같다.

1. 스택이 비어있는데 닫힌 괄호가 오는 경우

2. 스택 top에 있는 괄호에 짝이 맞지 않는 괄호가 오는 경우

3. 맨 마지막에 스택이 비어있지 않은 경우

 

 

코드

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

int ans = 0, tmp = 1;
string words;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    stack <char> st;
    bool error = false;
    getline(cin, words);
    for (int i = 0; i < words.length(); i++) {
        if( words[i] == '(') {
            st.push('(');
            tmp *= 2;
        }
        else if( words[i] == ')') {
            if (st.empty() || st.top() != '(') {
                error = true;
                break;
            }
            else {
                if( words[i-1] == '(') {
                    ans += tmp;
                }
                st.pop();
                tmp /= 2;
            }
        }

        else if( words[i] == '[') {
            st.push('[');
            tmp *= 3;
        }
        else if( words[i] == ']') {
            if (st.empty() || st.top() != '[') {
                error = true;
                break;
            }
            else {
                if( words[i-1] == '[') {
                    ans += tmp;
                }
                st.pop();
                tmp /= 3;
            }
        }
    }

    if (error || !st.empty()) {
        cout << 0;
    }
    else cout << ans;
    return 0;
}