백준 2504 G5 괄호의 값

문제: 괄호의 값

접근

올바른 괄호쌍을 찾는 문제는 보통 LIFO 구조인 스택을 이용하여 풀이한다.

이 문제는 그에 더해 서로 다른 두 괄호의 연속(예: ()[])과 중첩(예: [()])을 다르게 계산해야 한다.

예를 들어 (()[])에 대해서 생각해보자.

)와 ]을 만나면서, 가장 근처의 ( 혹은 [과 먼저 상쇄되며 계산이 진행된다.

주의할 점은 연속에 대해서는 그때 그때 값을 그대로 누적하여 더하면 되는데, 중첩에 대해서는 ( 혹은 [를 기억했다가, 나중에 곱해줘야 한다는 것이다.

( 혹은 [를 만날 때마다, 기억했다가, ) 혹은 ]를 만날 때마다 적절히 상쇄시켜야 한다.

이를 위해, 계산 값을 저장할 용도로 역시 자료구조 스택을 사용하고, 기억을 위한 용도로 (와 [를 위해 특정한 값을 매핑한다.

예를 들어 계산 값을 저장할 용도인 스택 num을 선언했다고 하자.

( 혹은 [를 만났을 때, 특정한 가짜 값을 스택에 우선 넣어 두고, ) 혹은 ]를 만날 때마다 상황에 맞게 처리하도록 한다.

(를 -2 라는 값으로, [를 -3이라는 값으로 표현하기로 해보자.

만일 지금 이 순간, )를 만나는 경우 아래와 같은 경우의 수가 있다.

• num의 최상단에 -2가 있다.
  • ()가 만들어진 경우이다.
  • 최상단의 -2를 num에서 빼고, ()의 값인 2를 num에 넣는다.
• num의 최상단에 -3이 있다.
  • [)의 경우로, 올바르지 않은 괄호쌍이다.
• num의 최상단에 -2나 -3 외의 숫자가 있다.
  • X)인 상황으로, 약간의 검사를 수행해야 (X) 인지, [X)인지, X)인지 알 수 있다.
  • num의 최상단이 -2이 될 때까지 최상단의 수를 임시로 계속 더한다.
  • 만일, -2를 찾는 중에 -3을 만나거나 num이 비어버리면, [X)이거나 X) 라는 올바르지 않은 괄호쌍이므로 종료한다.
  • -2를 제대로 찾았으면, -2까지도 num에서 팝 하고, 임시로 더한 값에 2를 곱하여 num에 다시 넣어준다.

]를 만나는 경우도 동일하다.

(()[[]])([]) 의 예시

최종적으로 스택 num 에는 [22, 6]이 남아있게 되는데, 따라서 답은 22 + 6 = 28이다. a

코드

코드가 좀 위아래로 길다

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

using namespace std;

/// @brief '(' 를 마킹하기 위한 매크로
#define S_OPEN -2

/// @brief '[' 를 마킹하기 위한 매크로
#define B_OPEN -3

int main() {
  string ps; cin >> ps;
  stack<int> num;

  int answer = 0;

  for (int i = 0; i < ps.size(); ++i) {
    // 열리는 경우 우선 마킹해 둔다
    if (ps[i] == '(') {
      num.push(S_OPEN);
    } 
    // 닫히는 경우의 적절한 처리 로직
    else if (ps[i] == ')') {
      
      // ')' 이면 가장 최근의 스택 최상단을 확인해봐야 하는데,
      // 스택이 비어있는 경우 최상단을 확인하는 경우 UB가 발생할 수 있음.
      if (num.empty()) {
        break;
      }

      // 가장 최근에 넣은게 일단 [이면,
      // 짝이 맞지 않는 것이므로 빠른 종료
      if (num.top() == B_OPEN) {
        break;
        // () 인 상황
      } else if (num.top() == S_OPEN) {
        num.pop();
        num.push(2);
        // (X) 인 상황
      } else {
        // 이제부터 `(`가 나올 때까지 스택을 훑을거임
        // 만일 스택 다 훑었는데 `(`가 안나오면 올바르지 않은 것임 
        int temp_sum = 0;
        bool is_invalid = true;
        while (!num.empty()) {
          if (num.top() == B_OPEN) {
            break;
          }

          if (num.top() != S_OPEN) {
            temp_sum += num.top();
            num.pop();
          // `(` 발견!
          // 임시로 더한 것들에 * 2 해서 다시 스택에 넣어줌
          } else {
            is_invalid = false;
            int temp = temp_sum * 2;
            num.pop();
            num.push(temp);
            break;
          }
        }

        if (is_invalid) {
          break;
        }
      }
    }
    // 열리는 경우 우선 마킹해 둔다
    else if (ps[i] == '[') {
      num.push(B_OPEN);
    }
    // 닫히는 경우 적절한 처리 로직
    else if (ps[i] == ']') {

      // ']' 이면 가장 최근의 스택 최상단을 확인해봐야 하는데,
      // 스택이 비어있는 경우 최상단을 확인하는 경우 UB가 발생할 수 있음.
      if (num.empty()) {
        break;
      }

      // 가장 최근에 넣은게 일단 (이면,
      // 짝이 맞지 않는 것이므로 빠른 종료
      if (num.top() == S_OPEN) {
        break;
        // [] 인 상황
      } else if (num.top() == B_OPEN) {
        num.pop();
        num.push(3);
        // [X] 인 상황
      } else {
        // 이제부터 `[`가 나올 때까지 스택을 훑을거임
        // 만일 스택 다 훑었는데 `[`가 안나오면 올바르지 않은 것임 
        int temp_sum = 0;
        bool is_invalid = true;
        // -3 까지 
        while (!num.empty()) {
          if (num.top() == S_OPEN) {
            break;
          }

          if (num.top() != B_OPEN) {
            temp_sum += num.top();
            num.pop();
          } else {
            // `]` 발견!
            // 임시로 더한 것들에 * 3 해서 다시 스택에 넣어줌
            is_invalid = false;
            int temp = temp_sum * 3;
            num.pop();
            num.push(temp);
            break;
          }
        }

        if (is_invalid) {
          break;
        }
      }
    }
  }

  // 괄호 훑기 끝!
  // 이제 스택에 남은 값들을 처리할 것임

  while (!num.empty()) {
    // 만일 마킹하려고 넣어둔 임시 값이 껴있다? 
    // 뭔가 잘못된 것이므로 0으로 종료
    if (num.top() == S_OPEN || num.top() == B_OPEN) {
      answer = 0;
      break;
    }
    answer += num.top();
    num.pop();
  }

  cout << answer;
}