[백준 2504] 괄호의 값

백준 2504번 - 괄호의 값

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

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

입력
첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.

출력
첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다. 

예제 입력 1 
(()[[]])([])
예제 출력 1 
28

예제 입력 2
[][]((])
0

---

✏️ 풀이

괄호를 보자마자 준비된 세트피스 플레이처럼 이건 스택문제다 라고 생각했다.
단, 늘 보던 문제가 아닌 살짝 다른 유형의 문제였다.
두 개의 괄호가 있었기 때문에 스택을 2개 사용해야하나 싶었고 조금 정석의 방법이 아닌 다른 방법으로 문제를 해결했던 것 같다.

아래는 나의 풀이 과정이다. 분배 법칙을 이용하는 방법이 있다고는 하지만 전혀 떠오르지도 않았고, 이 방법을 사용했기 때문에 사용한 방법으로 정리를 하겠다.

우선, 괄호를 저장할 stack<char>과 숫자를 저장할 stack<int> 2개를 전역변수로 선언한다.
stack에 들어갈 수는 괄호 외에 2와 3이라는 char뿐이다. 2와 3의 char는 숫자가 들어갔다라는 표시일 뿐 값과는 상관이 없다. 또한, check라는 bool 값은 올바른 괄호열인지를 체크해주는 변수이다.

1. 처음은 무조건 check=true로 올바른 괄호열임을 알린다.
2. 괄호열을 입력받고 for문으로 sentence.length()까지 for문을 돌린다.
3. 각 for문의 첫 번째 줄은 check==false이거나 sentence.length()가 홀수라면 break를 해주는 구문이다.(괄호열의 길이가 홀수라면 올바른 괄호열이 될 수 없다.)
4. '(', '['를 만나면 스택에 넣는다.
5. '()', '[]' 이렇게 붙어있는 괄호열이라면 숫자로 바꿔준다.
6. 그게 아닌 ')', ']'를 만난다면 '(', '['를 만날때까지 숫자들을 만나면 더해주면서 마지막엔 x2나 x3 연산을 수행해준다.

case 1, 2
'[', '('일 경우 input 스택에 바로 push한다.

case 3, 4
if input.empty()가 아니고 input.top()이 '('이고 현재 문자가 ')'이라면
-> '()', '[]'를 감지할 수 있음.
-> 이 경우 2나 3의 숫자를 output stack에 push해준다.
-> 또한 input stack에는 괄호를 지워주며 숫자를 삽입해준다.(나중에 연산할 때 필요)

case 5, 6
위에서 걸리는 경우가 아닌, ')', ']'를 만난다면,
'(', '['를 만날때까지 숫자를 만난다면 값을 더해준다.(결합된 괄호열)
그 후, x2나 x3 연산을 수행해준다. -> (X), [X]값에 대한 처리.

위 과정까지 글로 서술하면 이해가 어려울 수 있기 때문에 예제 입력1로 같이 문제를 풀어보자.

입력 : (()[[]])([])
for문으로 index를 하나씩 조회한다.  

index = 0, '('
stack input : (
stack output :

index = 1, '('
stack input : ( (
stack output :

index = 2, ')'
붙어있는 괄호가 나왔으므로, input.pop(), input.push('2'), output.push(2)
stack input : ( 2
stack output : 2

index = 3, '['
stack input : ( 2 [
stack output : 2

index = 4, '['
stack input : ( 2 [ [
stack output : 2

index = 5, ']'
붙어있는 괄호가 나왔으므로, input.pop(), input.push('3'), output.push(3)
stack input : ( 2 [ 3
stack output : 2 3

index = 6, ']'
붙어있지 않음. (숫자가 존재)
따라서 [] 사이의 숫자들을 더해주고 3을 곱해주면 됨.
output.pop(), input.pop() 동시에 수행.
그 후, 여는 괄호를 만나므로 x3을 수행한 뒤, output과 input에 push
input에 3을 push하는 이유는 그냥 값이 들어감을 알려주기 위함  
최종 계산할 값은 output stack에 들어감.  
stack input : ( 2 3
stack output : 2 9

index = 7, ')'
붙어있지 않음. (숫자가 존재)
따라서 '('를 만날떄까지 '()'사이의 값들을 다 더해주고 x2를 해주면 됨.
더해주는 값은 output의 값을 더해주면 됨. input은 체크용
즉, input의 '('를 만날때까지 숫자가 2개 있으니, output의 2개 수를 더해서 x2를 해주면 됨.  
2 + 9 = 11 -> 11 x 2 = 22
stack input : 2
stack output : 22

이제부턴 로직이 똑같으므로 빠르게 수행하겠음.

index = 8, '('
stack input : 2 (
stack output : 22

index = 9, '['
stack input : 2 ( [
stack output : 22

index = 10, ']'
stack input : 2 ( 3
stack output : 22 3

index = 11, ')'
stack input : 2 6
stack output : 22 6

for문이 끝났으므로, output의 값을 pop하면서 합계를 구해 출력해주면 된다.

출력 : 28 (6 + 22 = 28)

---

✔️ 정답 코드

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

using namespace std;

stack<char> input;
stack<int> output;
int a = 0; // (
int b = 0; // [
bool check = true;

int main(void) {
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);

   string sentence;
   cin >> sentence;

   for (int i = 0; i < sentence.length(); i++) {
      if (check == false || sentence.length()%2==1)
         break;
      if (sentence[i] == '(') {
         input.push(sentence[i]);
         continue;
      }
      else if (sentence[i] == '[') {
         input.push(sentence[i]);
         continue;
      }
      else if (!input.empty() && input.top() == '(' && sentence[i] == ')') {
         input.pop();
         input.push('2');
         output.push(2);
      }
      else if (!input.empty() && input.top() == '[' && sentence[i] == ']') {
         input.pop();
         input.push('3');
         output.push(3);
      }
      else if (sentence[i] == ')') {
         check = false;
         int sum = 0;
         while (1) {
            if (!input.empty() && input.top() == '(') {
               check = true;
               output.push(sum * 2);
               input.pop();
               input.push('2');
               break;
            }
            if (output.empty()) {
               check = false;
               break;
            }
            sum += output.top();
            output.pop();
            input.pop();
         }
      }
      else if (sentence[i] == ']') {
         check = false;
         int sum = 0;
         while (1) {
            if (!input.empty() && input.top() == '[') {
               check = true;
               output.push(sum * 3);
               input.pop();
               input.push('3');
               break;
            }
            if (output.empty()) {
               check = false;
               break;
            }
            sum += output.top();
            output.pop();
            input.pop();
         }
      }
   }

   if (!check) {
      cout << 0;
      return 0;
   }

   int sum = 0;
   while (!output.empty()) {
      sum += output.top();
      output.pop();
   }
   cout << sum;

   return 0;
}