백준 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 이다.

---

스택을 사용하는 유형 중 가장 일반적인 문제인 "괄호 판단하기"를 약간 변형시킨 문제이다.
기존의 "괄호 판단하기" 문제를 풀 때는 닫는 괄호(ex: ), }, ] )가 나왔을 때 스택에서 pop한 원소와 매칭이 되는지 확인했다면, 해당 문제는 추가적으로 원래 괄호 문자열에서 바로 이전 괄호와 매칭되는지를 확인해야 한다.

해당 문제를 풀기 위한 핵심 아이디어는 다음과 같다.

1. 열린 괄호를 스택에 넣을 때 2 또는 3을 곱하기

2. 닫힌 괄호의 경우 원래 괄호 문자열에서 바로 이전 괄호와 매칭되는 경우에만 계산 값 합하기

let fs = require("fs");
let input = fs
  .readFileSync('/dev/stdin')
  .toString()
  .split("")
// console.log(input);

let answer = 0;
let stack = [];
let i = 0;
let target;
let sum = 1;
while(i < input.length) {
    switch(input[i]) {
        case '(':
            stack.push(input[i]);
            sum *= 2;
            break;
        case '[':
            stack.push(input[i]);
            sum *= 3;
            break;
        case ')':
            target = stack.pop();
            if(target === '(') {
                if(input[i-1] === '(') answer += sum;
                sum  = parseInt(sum / 2);
            } else {
                return console.log(0);
            }
            break;
        case ']':
            target = stack.pop();
            if(target === '[') {
                if(input[i-1] === '[') answer += sum;
                sum  = parseInt(sum / 3);
            } else {
                return console.log(0);
            }
            break;
        default:
            break;
    }
    i++;
}

if (stack.length === 0) console.log(answer);
else console.log(0);