[백준 2504] 괄호의 값 - C++

문제접근

이 문제는 어떤 발상을 떠올리지 못하면 풀지 못하는 문제였다. 

예를 들어 [ [ ] [ ] ] 를 풀면, 3 * ( 3 + 3 ) 가 나오는데, 이 방식을 코딩으로 옮기기가 너무 힘들었다.

그래서 분배법칙을 이용해야 한다. 저 식을, 3 * 3 + 3 * 3 로 바꿀 수 있다. 이를 알고리즘으로 옮기면 된다.

 

[  뒤에 나오는 모든 값이 * 3이 된다

 

[ [  뒤에 나오는 모든 값이 * 3이 된다.

 

[ [ ]  ']'가 나왔으므로, 값을 빼야 한다. ans라는 변수에 지금까지 곱해진 " 3 * 3 " 을 넣는다. 또한, 한 세트가 끝났으므로, 뒤에 나오는 모든 값이 3 * 3 / 3 이 된다.

 

[ [ ] [ 뒤에 나오는 모든 값이 * 3 이 된다.

 

[ [ ] [ ] ']'가 나왔으므로, 값을 빼야 한다. ans라는 변수에 지금까지 곱해진 " 3 * 3 " 을 넣는다. 또한, 한 세트가 끝났으므로, 뒤에 나오는 모든 값이 3 * 3 / 3 이 된다.

 

[ [ ] [ ] ] ']'가 나왔는데, 바로 위에 케이스에서 이미 이 값까지 처리를 해버렸다. 따라서 이 케이스를 통해, 우리는 ' ] ' 가 나와도, 바로 앞에 ' [ ' 가 있어야지 값을 빼야 한다는 것을 알 수 있다. 이 경우까지 처리해서 구현을 해주면 된다.

 

ps. 끝까지 입력을 다 받았는데, [ [ ] 인 경우, 괄호 쌍이 맞지 않는다. 이 부분을 반례로 따로 처리해 주었다.

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

void solve() {
  string str;
  cin >> str;
  stack<char> s;
  int ans = 0;
  int multi = 1;
  bool isValid = true;
  for(int i = 0; i < str.size(); i ++) {
    char c = str[i];
    if(c == '(') {
      s.push(c);
      multi *= 2;
    } else if(c == '[') {
      s.push(c);
      multi *= 3;
    } else if(c == ')') {
        if(s.empty() || s.top() != '(') {
          isValid = false;
          ans = 0;
          break;
        }
        s.pop();
      if(str[i - 1] == '(') {
        ans += multi;
      }
      multi /= 2;
    } else if(c == ']') {
      if(s.empty() || s.top() != '[') {
          isValid = false;
          ans = 0;
          break;
      }
      s.pop();
      if(str[i - 1] == '[') {
        ans += multi;
      }
      multi /= 3;
    }
  }
  if(!s.empty()) ans = 0;
  cout << ans;
}

// ************************************

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  solve();
}

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