백준 2504 - 괄호의 값

문제 설명

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 이다.

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 괄호열이 주어지면 결과 값을 계산하면 된다.

계산 규칙은 다음과 같다.

• ()는 2이며 []는 3이다.
• (x)는 2 * x이다.
• [x]는 3 * x이다.

올바르지 않은 괄호열이라면 0을 출력한다.

 

올바른 괄호열을 계산하기 위해서는 스택을 사용하면 된다.

닫는 괄호가 나왔을 때 스택에 저장해 놓은 이전 괄호들을 하나씩 pop 하면서 쌍이 맞는지 확인하면 된다.

이 과정에서 짝을 찾지 못하였다면 해당 괄호열은 올바르지 않은 괄호열이다.

만약 알맞은 짝을 찾았다면 찾기 전까지 pop 한 요소들이 x에 해당한다.

즉, 짝을 찾기 전까지 요소를 모두 더해놓고 짝을 찾았을 때 2 또는 3을 곱해주면 된다.

()나 []같이 x가 아무것도 없을 수 있기 때문에 이에 대한 예외 처리를 해줘야 한다.

닫는 괄호에서 계산한 결괏값을 다시 스택에 넣어 값을 유지해주면 된다.

bool Pop(int type)
{
    int result = 0;
    int mult = 0;

    if (type == 0) mult = 2;
    else mult = 3;

    while (!bracket.empty())
    {
        auto top = bracket.back();
        bracket.pop_back();

        if (top == type)
        {
            if (result == 0) result = 1;
            bracket.push_back(result * mult);
            return true;
        }
        else
        {
            //올바르지 않은 괄호쌍
            if (top == 0 || top == 1)
            {
                cout << 0;
                exit(0);
            }

            result += top;
        }
    }

    return false;
}

 

정리하자면 여는 괄호는 스택에 그대로 추가하고 닫는 괄호가 나오면 짝을 찾기까지 x를 누적한다.

짝을 찾았다면 x에 2 또는 3을 곱해 최종 결과값을 만들고 이를 스택에 다시 추가한다.

 

모든 괄호를 살펴본 후 스택에 남아있는 값들을 모두 더하면 답을 찾을 수 있다.

이때, 여는 괄호가 남아있는 경우는 올바른 괄호열이 아니므로 0을 출력하고 종료한다.

int ans = 0;
for (auto num : bracket)
{
    if (num == 0 || num == 1)
    {
        cout << 0;
        return 0;
    }

    ans += num;
}

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;
string str;
vector<int> bracket;

bool Pop(int type)
{
    int result = 0;
    int mult = 0;

    if (type == 0) mult = 2;
    else mult = 3;

    while (!bracket.empty())
    {
        auto top = bracket.back();
        bracket.pop_back();

        if (top == type)
        {
            if (result == 0) result = 1;
            bracket.push_back(result * mult);
            return true;
        }
        else
        {
            //올바르지 않은 괄호쌍
            if (top == 0 || top == 1)
            {
                cout << 0;
                exit(0);
            }

            result += top;
        }
    }

    return false;
}

int main() 
{
    INPUT_OPTIMIZE;

    cin >> str;

    for (int i = 0; i < str.length(); i++)
    {
        auto current = str[i];
        if (current == '(')
        {
            bracket.push_back(0);
        }
        else if (current == '[')
        {
            bracket.push_back(1);
        }
        else if (current == ')')
        {
            if (!Pop(0))
            {
                cout << 0;
                return 0;
            }
        }
        else 
        {
            if (!Pop(1))
            {
                cout << 0;
                return 0;
            }
        }
    }

    int ans = 0;
    for (auto num : bracket)
    {
        if (num == 0 || num == 1)
        {
            cout << 0;
            return 0;
        }

        ans += num;
    }

    cout << ans;

    return 0;
}

---