백준 2504_괄호의 값

해당 문제 링크

)

문제 한 줄 요약

문자열의 괄호가 온전한 개수로 이루어졌는지 파악하고, 온전한 개수로 이루어졌을 경우 괄호들이 이루는 값을 구한다.

내가 생각한 조건

우선 스택을 써야 한다고 생각했다. 그 이유는 문자열을 입력받을 때 ) 또는 ]을 입력받아서 pop해야 할 경우, 가장 최근의 문자가 나와야 하기 때문이다.
그래서 괄호들을 저장하는 문자열 스택과 괄호로 인해 만들어지는 값을 저장하는 정수 스택을 따로 만들었다.
그리고 []과 ()처럼 연속되게 완전한 괄호가 만들어지는 경우를 따로 두고 계산하였는데, 이렇게 하니 코드 길이도 길어지고 연속으로 같은 기호가 나왔을 때 처리가 비효율적이어서 다시 생각해보았다.
그래서 (인 경우와 )로 나눠서 생각해 보았는데, (인 경우는 위와 동일하게 스택에 (를 넣고, )인 경우에 이전 문자열이 (인 경우와 그렇지 않은 경우로 고민하였다.

작성한 코드

#include <iostream>
#include <string>
#include <stack>
 
using namespace std;
 
int main()
{
    string str;
    stack<char> s;
    int ans = 0;
    int num = 1;
 
    cin >> str;
 
    for(int i = 0; i < str.size(); i++)
    {
        if(str[i] == '(')
        {
            s.push('(');
            num *= 2;
        }
        else if(str[i] == ')')
        {
            if(s.empty() || s.top() != '(')
            {
                cout << 0 << '\n';
                return 0;
            }
            else if(str[i-1] == '(')
            {
                s.pop();
                ans += num;
                num /= 2;
            }
            else if(str[i-1] != '(')
            {
                num /= 2;
                s.pop();
            }
        }
        else if(str[i] == '[')
        {
            s.push('[');
            num *= 3;
        }
        else if(str[i] == ']')
        {
            if(s.empty() || s.top() != '[')
            {
                cout << 0 << '\n';
                return 0;
            }
            else if(str[i-1] == '[')
            {
                s.pop();
                ans += num;
                num /= 3;
            }
            else if(str[i-1] != '[')
            {
                num /= 3;
                s.pop();
            }
        }
    }
 
    if(!s.empty())
    {
        cout << 0 << '\n';
        return 0;
    }
    cout << ans << '\n';
}

코드 작성 후 피드백

분배법칙을 생각해야 하는 것이 문제의 포인트였다. 괄호가 여러 개로 중첩될 경우 그 전에 계산한 값(tmp)을 초기화해서 다음 계산식에 활용할 수 있도록 하는 부분이 문제 해결의 포인트였다.
그래서 해당 링크를 참고한 결과, 기호가 중첩되는 상황에서 해당 기호를 닫는 괄호가 나온다면 해당 부분까지 계산한 값을 더해주면 되는 것이다.
(이 때 ]]이런 식으로 닫는 괄호가 중첩된다면 계산한 값(tmp)이 괄호 종류에 맞게 2 또는 3으로 나눠지므로 자연스럽게 tmp를 초기화할 수 있다.)
다시 풀어봐서 이런 방법도 있다는 것을 익혀야 할 것 같은 문제였다.

참조
()처럼 연속된 괄호의 경우의 수를 둔 경우
분배법칙 관련 링크