[백준] 2504번 : 괄호의 값

Kim Yuhyeon·2024년 1월 21일

알고리즘 + 자료구조

목록 보기

154/161

문제

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

접근 방법

먼저 stack을 이용해 올바른 괄호열인지 판단한다.

짝이 맞으면 pop

아니면 push

empty 면 올바른 괄호이다.

top 을 체크할 때 empty를 함께 체크하여서 런타임 에러가 나지 않도록 주의하자

다음은 괄호열의 값을 계산한다.

곱해주는 값 temp = 1
괄호가 열리면 해당하는 값을 temp에 곱해준다.
괄호가 닫히면
- 해당 위치 바로 앞 괄호가 짝이 맞는 열리는 괄호일 경우에만 temp의 값을 result에 더해준다.
- temp를 다시 해당하는 괄호열의 값으로 나눠준다.

예시 - `(()[[]])([])`

result = 0, temp = 1

(
result = 0, temp = 1*2 = 2

((
result = 0, temp = 2*2 = 4

(()
result = 0+4 = 4, temp = 4/2 = 2

(()[
result = 4, temp = 2*3 = 6

(()[[
result = 4, temp = 6*3 = 18

(()[[]
result = 4+18 = 22, temp = 18/3 = 6

(()[[]]
result = 22, temp = 6/3 = 2

(()[[]])
result = 22, temp = 2/2 = 1

(()[[]])(
result = 22, temp = 1*2 = 2

(()[[]])([
result = 22, temp = 2*3 = 6

(()[[]])([]
result = 22+6 = 28, temp = 6/3 = 2

(()[[]])([])
result = 28, temp = 2/2 = 1

풀이

#include <iostream>
#include <stack>
#include <string>

using namespace std;

string str;
char left2 = '(';
char left3 = '[';
char right2 = ')';
char right3 = ']';

void fastIO()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

bool isRightBlanket(string str) 
{

    stack<char> s;
    for(char ch : str) 
    {
        if (ch == left2 || ch == left3)
        {
            s.push(ch);
        }
        else if (ch == right2) 
        {
            if (!s.empty() && s.top() == left2)
            {
                s.pop();
            }
            else // 비어있거나 top이 left3이 아닌 경우 
            {
                s.push(ch);
            }
        }
        else if (ch == right3) 
        {
            if (!s.empty() && s.top() == left3)
            {
                s.pop();
            }
            else 
            {
                s.push(ch);
            }
        }
    }

    return s.empty();
}

int solve(string str) 
{
    if (!isRightBlanket(str))
    {
        return 0;
    }

    int result = 0;
    int temp = 1;

    for(int i=0; i<str.length(); i++)
    {
        char target = str[i];
        if (target == left2)
        {
            temp *= 2;
        }
        else if (target == left3) 
        {
            temp *= 3;
        }
        else if (target == right2)
        {
            if (str[i-1] == left2)
            {
                result += temp;
            }
            temp /= 2;
        }
        else if (target == right3)
        {
            if (str[i-1] == left3)
            {
                result += temp;
            }
            temp /= 3;
        }
        
    }

    return result;
}

void output(string str)
{
    cout << solve(str) << '\n';
}

void input() 
{
    cin >> str;
    output(str);
}

int main() 
{
    fastIO();
    input();

    return 0;
}