2504 괄호의 값

문제

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.

1. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.
2. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다.
3. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.

예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다.

1. ‘()’ 인 괄호열의 값은 2이다.
2. ‘[]’ 인 괄호열의 값은 3이다.
3. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
4. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.

여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다.

====

문제 풀이

기존 괄호 문제에서는 스택을 활용하여 열림은 스택에 넣고 닫힘을 만나면 스택의 마지막 요소를 끄집어 내면서 계산해줬다.

하지만 이 문제에는  깊이에 따른 계산 방식이 다르다는 점을 유념 해줘야 한다는 차이점이 있다.

자식 요소들은 모두 더해주고 이후에는 곱해주는 방식이다.

따라서 스택에 열림을 넣을 땐 깊이까지 표시해줬다. 깊이는 스택 마지막 요소의 깊이에 +1을 해주면 된다. 각 깊이별로 계산된 값을 기록해줄 stage 배열을 길이가 최대 15만큼 생성해준다. (입력값의 길이가 최대 30이므로 생길 수 있는 최대 깊이는 15 이다) 이후 닫힘을 만나서 스택 마지막 요소를 Pop 했을 때, 그 깊이의 +1이 stage에 기록되어 있다면 자식이 있었다는 것이므로 현재 과호의 값을 곱해주면 된다. 자식을 처리했으니 그 stage[depth+1]은 0으로 할당해준다. 

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const arr = input[0].split('');
const n = input.length;

let result = 0;

const isOpen = (ch) => ch === '(' || ch === '[';
const matchOpen = (ch) => {
    switch (ch) {
        case ')': {
            return '(';
        }
        default: {
            return '[';
        }
    }
};

let s = 0;
const stack = [];

while (arr.length) {
    const v = arr.shift();
    const stage = Array.from({ length: 15 }, () => 0);
    if (!isOpen(v)) {
        console.log(0);
        process.exit(0);
    }
    stack.push([v, 0]);
    while (stack.length && arr.length) {
        const v = arr.shift();
        if (isOpen(v)) {
            stack.push([v, stack.at(-1)[1] + 1]);
        } else {
            const [op, depth] = stack.pop();
            if (matchOpen(v) !== op) {
                console.log(0);
                process.exit(0);
            }
            const value = op === '(' ? 2 : 3;
            if (stage[depth + 1]) {
                stage[depth] += value * stage[depth + 1];
                stage[depth + 1] = 0;
            } else {
                stage[depth] += value;
            }
        }
    }
    result += stage[0];
}

console.log(result);