[백준] 2504. 괄호의 값

문제 링크

[백준] 2504. 괄호의 값

풀이 과정

스택 문제입니다.

let err = false;
let sum = 0, tmp = 1;
let stack = [];

사용한 변수는 위와 같습니다.

• err 는 잘못된 괄호쌍일 경우, true를 저장합니다.
• sum 은 괄호들을 순회하며, 현재까지 값이 계산된 누적 괄호값을 담고 있습니다.
• tmp 는 여는 괄호부터 닫는 괄호를 만나기까지의 부분 괄호값을 저장하는데 사용합니다.
• stack 은 스택 역할을 하는 배열입니다.

if (ch === "[") {
    stack.push(ch);
    tmp *= 3;
} else if (ch === "(") {
    stack.push(ch);
    tmp *= 2;
}

여는 괄호일 경우, 스택에 해당 괄호를 push하고 tmp 에 각 괄호열의 값을 적용시켜 줍니다.

else if (ch === "]") {
    if (stack.length === 0) {
        err = true;
        sum = 0;
        break;
    }

    if (stack[stack.length - 1] === "[") {
        if (s[i - 1] === "[") sum += tmp;
        stack.pop();
        tmp /= 3;
    } else {
        err = true;
        break;
    }
} else if (ch === ")") {
    if (stack.length === 0) {
        err = true;
        sum = 0;
        break;
    }

    if (stack[stack.length - 1] === "(") {
        if (s[i - 1] === "(") sum += tmp;
        stack.pop();
        tmp /= 2;
    } else {
        err = true;
        break;
    }
}

닫는 괄호의 경우는 다음 두 가지를 확인합니다.

• 먼저, 스택이 비어있다면, 올바른 괄호쌍이 아니므로 중단합니다.
• 스택이 비어있지 않다면, 다음과 같이 스택의 top을 비교합니다.
  • 스택 top이 닫는 괄호와 매칭되는 여는 괄호일 경우, tmp를 sum에 누적시킨 뒤, tmp를 해당 괄호값만큼 나누어 depth를 빠져 나옵니다.
  • 매칭되지 않는다면, 올바른 괄호쌍이 아니므로 중단합니다.

코드

const fs = require("fs");
const stdin = (process.platform === "linux" ? fs.readFileSync("/dev/stdin") : `({})`).toString().trim().split("\n");
const input = (() => {
    let line = 0;
    return () => stdin[line++];
})();

const s = input().split("");
let err = false;
let sum = 0,
    tmp = 1;
let stack = [];

for (let i = 0; i < s.length; i++) {
    let ch = s[i];

    if (ch === "[") {
        stack.push(ch);
        tmp *= 3;
    } else if (ch === "(") {
        stack.push(ch);
        tmp *= 2;
    } else if (ch === "]") {
        if (stack.length === 0) {
            err = true;
            sum = 0;
            break;
        }

        if (stack[stack.length - 1] === "[") {
            if (s[i - 1] === "[") sum += tmp;
            stack.pop();
            tmp /= 3;
        } else {
            err = true;
            break;
        }
    } else if (ch === ")") {
        if (stack.length === 0) {
            err = true;
            sum = 0;
            break;
        }

        if (stack[stack.length - 1] === "(") {
            if (s[i - 1] === "(") sum += tmp;
            stack.pop();
            tmp /= 2;
        } else {
            err = true;
            break;
        }
    }
}

if (err || stack.length) console.log(0);
else console.log(sum);