[백준] 2504 괄호의 값 - javascript

📌 문제

https://www.acmicpc.net/problem/2504

📌 풀이

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

let arr = input[0].split('');
let stack = [];

for (let i = 0; i < arr.length; i++) {
  if (stack.length === 0 && (arr[i] === ')' || arr[i] === ']')) {
    console.log(0);
    exit();
  }

  if (arr[i] === '(' || arr[i] === '[') stack.push(arr[i]);

  if (arr[i] === ')') {
    if (stack[stack.length - 1] === '(') {
      stack.pop();
      stack.push(2);
    } else if (
      stack[stack.length - 2] === '(' &&
      stack[stack.length - 1] !== '['
    ) {
      const num = stack.pop();
      stack.pop();
      stack.push(2 * num);
    } else {
      console.log(0);
      exit();
    }
  }

  if (arr[i] === ']') {
    if (stack[stack.length - 1] === '[') {
      stack.pop();
      stack.push(3);
    } else if (
      stack[stack.length - 2] === '[' &&
      stack[stack.length - 1] !== '('
    ) {
      const num = stack.pop();
      stack.pop();
      stack.push(3 * num);
    } else {
      console.log(0);
      exit();
    }
  }

  if (
    typeof stack[stack.length - 1] === 'number' &&
    typeof stack[stack.length - 2] === 'number'
  ) {
    const num = stack[stack.length - 1] + stack[stack.length - 2];
    stack.pop();
    stack.pop();
    stack.push(num);
  }
}
if (stack.length !== 1 || typeof stack[0] !== 'number') {
  console.log(0);
} else {
  console.log(stack[0]);
}

✔ 알고리즘 : 구현 + 스택

✔ 끝나는 괄호가 들어오는데 stack이 비어있는 경우는 불가능한 경우이므로 0을 출력한다.

✔ (나 [와 같이 시작하는 괄호가 들어올 때는 무조건 stack에 push 한다.

✔ ) 나 ] 모두 동일한 경우의 수를 가진다.
ex) ] 인 경우

• 스택의 최상단이 ( 일 때
  불가능한 경우이므로 0을 출력
• 스택의 최상단이 [ 일 때
  이 때는 단순히 [ 를 pop 해준 후 stack에 []인 값인 3을 push

if (arr[i] === ']') {
    if (stack[stack.length - 1] === '[') {
      stack.pop();
      stack.push(3);
    } 
  }

• 스택의 최상단이 number 이고 두번째 상단이 [ 일 때
  pop을 두 번 하고 number * 3을 push

if (arr[i] === ']') {
  	 ... 위의 if 문 통과 후
     else if (
      stack[stack.length - 2] === '[' &&
      stack[stack.length - 1] !== '('
    ) {
      const num = stack.pop();
      stack.pop();
      stack.push(3 * num);
    } 
  }

• 스택의 최상단이 ( 일 때 || 스택의 최상단이 number 이고 두번째 상단이 ( 일 때
  불가능한 경우이므로 0을 출력

if (arr[i] === ']') {
     ... 위의 if 문 통과 후
     else {
      console.log(0);
      exit();
    }
  }

✔ for문의 마지막에서는 항상 stack의 최상단과 그 밑을 확인하여 괄호 사이에 number가 두 개 이상 들어가지 못하도록 한다.

if (
    typeof stack[stack.length - 1] === 'number' &&
    typeof stack[stack.length - 2] === 'number'
  ) {
    const num = stack[stack.length - 1] + stack[stack.length - 2];
    stack.pop();
    stack.pop();
    stack.push(num);
  }

❗ stack의 길이가 1이 아니거나 길이는 1이지만 stack[0]이 괄호인 경우는 올바르지 못한 괄호열이다.

if (stack.length !== 1 || typeof stack[0] !== 'number') {
  console.log(0);
} 

✔ 위의 조건을 다 통과하면 stack은 길이가 1이고 stack[0]은 number 이므로 stack[0]을 출력

✔ 난이도 : 백준 기준 실버 2