[백준 C++] 2054번 괄호의 값

괄호의 값

한 시간 안에 푸는 연습을 했는데 정신을 차리고 보니 네 시간이 지나 있었다.

전에 괄호로 이루어진 문자열이 올바른 괄호 문자열인지 판단하는 문제가 있었는데 그 문제를 조금 더 심화시킨 문제다. 그 문제에서는 '(' 와 ')' 만 쓰였다면, 이 문제에서는 '(', ')', '[', ']' 가 쓰인다. 또한 괄호의 조합에 따라 계산을 또 해야해서 문제 자체는 재미있었지만 복잡했다.

문제를 풀고 다른 사람의 풀이를 보니 나처럼 푼 사람이 잘 없어서 좀 자세하게 남기고자 한다. 표로 이해하는 게 더 쉬울 것 같다. 표를 보자.

1. 스택을 두 개 선언했다. 하나는 괄호를 쌓는 곳, 나머지 하나는 계산 결과를 담고자 만든 것이다.  두 번째 설명이 좀 애매한데 예를 들어, 예제 입력 1에서 $(()[[]])([])$ 빨간색으로 표신한 부분에서 tmp 에 0을 push 한다.

2. stack s 가 비어있다면, ch[i] 를 s 에 push 하고, tmp 에도 0 을 push 한다.

3. stack s 가 비어있지 않다면, ch[i] 가 isPair 인지 확인한다. ()나 [] 라면 참이다.

4. isPair 가 참이라면, stack s 를 pop 한다. 그리고 tmp 에 더할 값을 계산한다. 여기서는 괄호가 괄호 안에 다른 괄호를 포함하고 있는지 확인한다. 괄호를 포함하고 있지 않다면 그냥 괄호에 따라 2 나 3 을 더하면 된다. 하지만 괄호를 포함하고 있다면, tmp 의 top에 2 나 3 을 곱한다. nesting 이 하나 끝난 것이므로 tmp 의 top 값을 다음 top에 더해준다.

5. isPair 가 거짓이라면, stack s 에 ch[i] 를 push 한다. 그리고 여는 괄호가 연속적(isSuccessive)으로 등장한 것이었다면 tmp 에 0 을 한번 더 더해준다.

표

문과생인데 필력이 똥이라서 표로 예제 1이 어떻게 계산되는지 시각화했다.

char index	0	1	2	3	4	5	6	7	8	9	10	11
char	(	(	)	[	[	]	]	)	(	[	]	)
stack s	(
stack tmp	0

stack s 가 비어있었으므로 s와 tmp 모두 push 한다.

char index	0	1	2	3	4	5	6	7	8	9	10	11
char	(	(	)	[	[	]	]	)	(	[	]	)
stack s	(	(
stack tmp	0	0

stack s 의 top 과 합쳐봤을 때 () 이나 [] 이 되지 않고(isPair = false), 여는 괄호가 연속적으로 등장했으므로(isSuccessive = true) s와 tmp 모두 push 한다.

char index	0	1	2	3	4	5	6	7	8	9	10	11
char	(	(	)	[	[	]	]	)	(	[	]	)
stack s	(
stack tmp	0	2

isPair가 참이므로 s 를 pop. 괄호 안에 다른 괄호를 포함하고 있지 않으므로(isNesting = false) tmp 에 2를 더한다.

char index	0	1	2	3	4	5	6	7	8	9	10	11
char	(	(	)	[	[	]	]	)	(	[	]	)
stack s	(	[
stack tmp	0	2

isPair 가 거짓이므로 s 에 push. isSuccessive 도 거짓이므로 tmp는 그대로 둔다.

char index	0	1	2	3	4	5	6	7	8	9	10	11
char	(	(	)	[	[	]	]	)	(	[	]	)
stack s	(	[	[
stack tmp	0	2	0

isPair 가 거짓이므로 s 에 push. isSuccessive 는 참이므로 tmp 에 0 을 더한다.

char index	0	1	2	3	4	5	6	7	8	9	10	11
char	(	(	)	[	[	]	]	)	(	[	]	)
stack s	(	[
stack tmp	0	2	3

isPair 가 참이므로 s 를 pop. isNesting 은 거짓이므로 tmp 의 top 에 3 을 더해준다.

char index	0	1	2	3	4	5	6	7	8	9	10	11
char	(	(	)	[	[	]	]	)	(	[	]	)
stack s	(
stack tmp	0	11

isPair 가 참이므로 s 를 pop. isNesting 이 참이므로 tmp 의 top 에 3 을 곱해준다. 그 후 tmp 의 top 을 그 다음 top 에 더해준다.

char index	0	1	2	3	4	5	6	7	8	9	10	11
char	(	(	)	[	[	]	]	)	(	[	]	)
stack s
stack tmp	22

isPair 가 참이므로 s 를 pop. isNesting 이 참이므로 tmp 의 top 에 2 를 곱해준다. 그 후 tmp 의 top 을 그 다음 top 에 더해준다.

char index	0	1	2	3	4	5	6	7	8	9	10	11
char	(	(	)	[	[	]	]	)	(	[	]	)
stack s	(
stack tmp	22	0

stack s 가 비어있었으므로 s와 tmp 모두 push 한다.

char index	0	1	2	3	4	5	6	7	8	9	10	11
char	(	(	)	[	[	]	]	)	(	[	]	)
stack s	(	[
stack tmp	22	0	0

isPair 가 거짓이므로 s 에 push. isSuccessive 는 참이므로 tmp 에 0 push 한다.

char index	0	1	2	3	4	5	6	7	8	9	10	11
char	(	(	)	[	[	]	]	)	(	[	]	)
stack s	(
stack tmp	22	0	3

isPair가 참이므로 s 를 pop. isNesting이 거짓이므로 tmp 에 3 을 더한다.

char index	0	1	2	3	4	5	6	7	8	9	10	11
char	(	(	)	[	[	]	]	)	(	[	]	)
stack s
stack tmp	22	6

isPair 가 참이므로 s 를 pop. isNesting 이 참이므로 tmp 의 top 에 2 를 곱해준다. 그 후 tmp 의 top 을 그 다음 top 에 더해준다.

이 시점에서 stack s 에 원소가 들어 있다면 0을 출력하고, 그렇지 않다면 stack tmp 에 든 값을 모두 더하여 출력하면 된다.

#include <iostream>
#include <stack>
#include <cstring> // strlen
#include <stdlib.h> // abs
using namespace std;
 
stack<char> s;
// tmp stacks temporary value for calculating the answer.
// if s is empty or left bracket appear successive, push 0 to tmp.
stack<int> tmp;
int ans = 0;
char ch[32];
 
// () or [] => 2 or 3
bool isPair(const char &top, const char &ch) {
  return (ch - top == 1 || ch - top == 2);
}
 
// [( or ([ or [[ or (( is successive.
// this is for judging whether left bracket successive.
bool isSuccessive(const char *ch) {
  return (*ch - *(ch - 1) == 0 || abs(*ch - *(ch - 1)) == 51);
}
 
// )] or ]) or ]] or )) is nesting.
bool isNesting(const char *ch) {
  return (*ch - *(ch - 1) == 0 || abs(*ch - *(ch - 1)) == 52);
}
 
// if nesting, multiply. if not, add.
void addVal(const char &ch) {
  if (!isNesting(&ch)) {
    if (ch == ')') tmp.top() += 2;
    else tmp.top() += 3;
  } else {
    if (ch == ')') tmp.top() *= 2;
    else tmp.top() *= 3;
    // after multiplying, add top value to the next top.
    int a = tmp.top();
    tmp.pop();
    if (!tmp.empty()) tmp.top() += a;
  }
}
 
int main() {
  cin.tie(NULL);
  ios::sync_with_stdio(false);
 
  cin >> ch;
 
  for (int i = 0; i< strlen(ch); i++) {
    if (s.empty()) {
      s.push(ch[i]);
      tmp.push(0);
    }
    else {
       if (isPair(s.top(), ch[i])) {
        s.pop();
        addVal(ch[i]);
      } else {
        s.push(ch[i]);
        if (isSuccessive(&ch[i])) tmp.push(0);
      }
    }
  }
 
  if (!s.empty()) cout << 0 << '\n';
  else  {
    while (!tmp.empty()) {
      ans += tmp.top();
      tmp.pop();
    }
    cout << ans << '\n';
  }
 
  return 0;
}