[BOJ] 2504: 괄호의 값

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

 

 

 

 

#include <bits/stdc++.h>
using namespace std;
string str;
stack<char> st;
int result, num = 1, valid = 1;

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

  cin >> str;
  for (int i = 0; i < str.length(); i++) {
    if (str[i] == '(') {
      num *= 2;
      st.push(str[i]);
    } else if (str[i] == '[') {
      num *= 3;
      st.push(str[i]);
    } else if (str[i] == ')') {
      if (st.empty() || st.top() != '(') {
        cout << 0;
        return 0;
      }
      if (str[i - 1] == '(') result += num;
      st.pop();
      num /= 2;
    } else {
      if (st.empty() || st.top() != '[') {
        cout << 0;
        return 0;
      }
      if (str[i - 1] == '[') result += num;
      st.pop();
      num /= 3;
    }
  }
  if (st.empty())
    cout << result << '\n';
  else
    cout << 0 << '\n';
}

괄호의 값을 분배법칙을 이용해서 풀려고 시도했다.

(()[[]])([])

문제의 입력이 위와 같을 때 괄호의 값은 (2 + 3 * 3) * 2 + 2 * 2이 된다.

위 식에 분배법칙을 적용한다면 2 * 2 + 2 * 3 * 3 + 2 * 2가 될 것이다.

 

주어진 입력과 분배법칙을 적용한 식을 비교해보면 2 또는 3이 곱해지는 개수가 열린 괄호의 개수와 비슷하다는 것을 알 수 있다.

좀 더 깊게 생각해보면 스택에 들어 있는 괄호들의 곱이라는 것을 알 수 있다.

즉 스택에 '(', '(' 이 들어 있다면 2 * 2가 되고, '(', '[', '[' 가 들어있다면 2 * 3 * 3이 되는 것이다.

 

코드로 구현하자면 열린 괄호는 무조건 스택에 push하고, 각 괄호가 가지는 값을 num에 곱한다.

=> '(' 는 2, '[' 는 3

 

닫힌 괄호는 스택의 탑과 비교해서 짝이 맞지 않으면 맞는 괄호쌍이 아니므로 0을 출력하고 프로그램을 종료한다.

 

괄호쌍이 맞다면 (), [] 처럼 연속하는 쌍인지 확인하고 참이라면 result에 num을 더해야 한다.

=> 식과 비교해모녀 (), [] 부분이 곱의 마지막이기 때문

 

이후에는 pop 연산과 num의 값을 다시 조정해야 한다.

그 이유는 현재 괄호가 올바른 괄호쌍이기 때문에 pop 연산을 수행해야 한다.

또 pop 연산을 수행하면 괄호 하나가 스택에서 제거되기 때문에 제거된 괄호의 값에 맞게 num을 나눠야 한다.

 

위 과정을 반복해서 반복문이 종료되면 st.empty()로 스택에 비었는지를 판단하고 1이면 result를 0이면 0을 반환한다.