[ 백준 ] 2504 / 괄호의 값

金弘均·2021년 9월 16일
0

Baekjoon Online Judge

목록 보기
176/228
post-thumbnail

# Appreciation

/*
 * Problem :: 2504 / 괄호의 값
 *
 * Kind :: Data Structure
 *
 * Insight
 * - 1. 올바른 괄호열인지 검사
 *   2. 괄호열의 값을 계산
 *   + Stack 을 이용하자
 *     # 올바른 괄호쌍인지 알아보는 것과 괄호의 값을 계산하기 위해서는
 *       현재 다루고 있는 괄호 또는 값의 가장 최근의 괄호 또는 값을 알고있어야 한다
 *
 * Point
 * - 검사와 계산을 분리할 수도 있고 같이할 수도 있다
 *   + 처음 풀때는 분리해서, 다시 풀때는 같이 하는 식으로 풀면
 *     실력향상에 더욱더 도움이 될 것 같다 :)
 *
 * - (()[]) 를 쉽게 계산하려면 어떻게 할까?
 *   + (
 *     ((
 *     (() => (2
 *     (2[
 *     (2[] => (23
 *     (23) => (5) => 10
 *     # Python 에서는 위 방식으로 풀기 쉽지만... C++ 은 아니다
 *   + 위의 괄호열은 (...) 로 나타낼 수 있다
 *     여기서 ... 에는 계산한 괄호의 값이 들어가는데
 *     바깥의 괄호인 '()' 에 의해 여기에 2를 곱해야 한다
 *     # 그럼 이 바깥의 괄호들을 offset 으로 생각해볼 수 있지 않을까?
 *       ((...)) 라면 4를 곱해야 하고
 *       (((...))) 라면 8을 곱해야 한다
 *       -> offset 을 항상 가지고 있으면 그 괄호의 값을 즉시 구할 수 있다
 *          (           / offset = 2, ans = 0
 *          ((          / offset = 4, ans = 0
 *          (() => (    / offset = 2, ans = 4
 *          ([          / offset = 6, ans = 4
 *          ([] => (    / offset = 2, ans = 4+6 = 10
 *          () => empty / offset = 1, ans = 10
 *          empty       / offset = 1, ans = 10
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <stack>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    string s; cin >> s;

    // Process
    stack<char> st;
    int ans = 0 /* 총 괄호의 값 */, offset = 1 /* 현재 오프셋 값 */;
    bool isRight = true; /* 올바른 괄호열의 여부 */
    for (int i=0; i<s.length(); i++) {
        char c = s[i]; /* 현재 다루는 괄호 */
        
        /* '(' 의 경우, 오프셋 2배, stack 에 '(' 추가 */
        if (c == '(') { offset *= 2; st.push('('); }
        
        /* '[' 의 경우, 오프셋 3배, stack 에 '[' 추가 */
        if (c == '[') { offset *= 3; st.push('['); }
        
        /* ')' 의 경우 */
        if (c == ')') {
            /* stack 이 비었거나 top 이 '(' 가 아니면 */
            if (st.empty() || st.top() != '(') {
                isRight = false; /* 올바르지 않은 괄호열 */
                break;
            }
            offset /= 2; /* 오프셋 1/2 로 감소 */
            if (i > 0 && s[i-1] == '(') { /* '()' 괄호열이면 */
                ans += offset * 2; /* 총 괄호의 값에 오프셋 * '()' 괄호열의 값 더해줌 */
            }
            st.pop(); /* 현재 stack 의 top '(' 제거 */
        }
        
        /* ']' 의 경우 */
        if (c == ']') {
            /* stack 이 비었거나 top 이 ']' 가 아니면 */
            if (st.empty() || st.top() != '[') {
                isRight = false; /* 올바르지 않은 괄호열 */
                break;
            }
            offset /= 3; /* 오프셋 1/3 로 감소 */
            if (i > 0 && s[i-1] == '[') { /* '[]' 괄호열이면 */
                ans += offset * 3; /* 총 괄호의 값에 오프셋 * '[]' 괄호열의 값 더해줌 */
            }
            st.pop(); /* 현재 stack 의 top '[' 제거 */
        }
    }
    /* 괄호열의 전부 순회했는데 stack 이 비어있지 않으면 */
    if (not(st.empty())) {
        isRight = false; /* 올바르지 않은 괄호열 */
    }

    // Control : Output
    cout << ((isRight) ? ans : 0) << endl;
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글