Algorithm

[BaekJoon / C++] 2504번 : 괄호의 값

송만덕 2021. 10. 19. 16:26

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

 

2504번: 괄호의 값

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

www.acmicpc.net


문제

 

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을 출력해야 한다.


풀이

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
int bracket(string &str)
{
    int sum = 0 , len = str.length();        //len = str의 길이
    int i,temp =1;
    vector<char> stk;        //스택 관리를 위한 vector
 
    for (i = 0; i < len; i++)
    {
        if (str[i] == '(')
        {
            temp *= 2;
            stk.push_back(str[i]);
        }
        else if (str[i] == '[')
        {
            temp *= 3;
            stk.push_back(str[i]);
        }
        else if (str[i] == ')')
        {
            if (stk.size() == 0 || stk.back() != '(')        //잘못된 입력일 시 return 0
                return 0;
            else
            {
                if (str[i-1== '(')        //분배법칙을 위한 조건문
                    sum += temp;
                temp /= 2;
                stk.pop_back();
            }
        }
        else if (str[i] == ']')
        {
            if (stk.size() == 0 || stk.back() != '[')
                return 0;
            else
            {
                if (str[i - 1== '[')
                    sum += temp;
                temp /= 3;
                stk.pop_back();
            }
        }
    }
 
    if (stk.size() == 0) //스택이 비지 않았다면 잘못된 입력
        return sum;
    else
        return 0;
}
 
int main()
{
    string str;
    cin >> str;
    cout << bracket(str) << "\n";
}
 
cs

 

무선 문제를 읽어 본 후 바로 스택을 사용하여 풀이해야 한 다는 점을 알 수 있었다.

 

하지만 괄호 입력에 따라 덧셈과 곱셈 연산이 다르기 때문에 이를 처리하기 위해 여러가지 방법을 생각해 보았는데,

 

첫번째는 재귀함수를 통해 직관적으로 구현하여 볼까 하다가 변수 관리가 너무 복잡해 질 것 같아 단순 반복문을 통해 조건식에 따라 구현하기로 하였다.

 

우선 문제의 예제 중 ( ( ) [ [ ] ] ) ( [ ] )와 같은 입력이 있는데, 이는 2(2+(3x3))+(2x3)이 되고

분배법칙을 통해 풀어보면 (2x2) + (2x3x3) + (2x3)이 된다.

 

이렇듯 분배법칙을 사용해 나타나는 식을 조건에 따라 동일하게 계산되게 하였고, 조건을 판별하기 위하여 스택을 사용하였는데

 

stack STL을 사용할까 하다가 vector STL을 사용하는 것이 스택의 값을 확인하기가 간편하다고 판단되어 vector를 사용하였다.

 

조건 중 중요한 부분은 31번과 43번 라인인데, 이 때는 스택에 따른 조건이 아닌 입력된 string에 의한 조건인데, 직전에 push된 괄호가 아닌 경우 덧셈을 하지 않음으로써 분배법칙에 따라 계산되게 하는 조건이다.

 

또 잘못된 입력으로 판단되는 조건이라 판단될 시 0를 곧바로 return하게 하였다.

댓글수0