백준 2504번 괄호의 값 - node.js

해당 포스팅은 백준 2504번 괄호의 값 풀이를 다룬다. 문제 링크
코드는 javascript로 작성하였다.

문제

• 괄호열은 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어진다.

• 올바른 괄호열

  • 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’
  • X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열
  • X와 Y 모두 올바른 괄호열이라면 XY도 올바른 괄호열

• 괄호열의 값

  • '()' 괄호열 값은 2
  • '[]' 괄호열 값은 3
  • ‘(X)’ 의 괄호값은 2×값(X)
  • ‘[X]’ 의 괄호값은 3×값(X)

주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하자.

입력

첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.

출력

• 첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다.
• 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다.

풀이

괄호열을 앞에서부터 탐색한다. 여는 괄호가 나오면 스택에 삽입하고, 닫는 괄호가 나오면 짝괄호를 찾아 연산을 한다음 pop한다.
핵심은 stack에 괄호들을 넣어주면서 짝이 맞을 시 괄호 대신 숫자를 넣는다는 것이다.

• 괄호열을 넣어줄 stack과 값을 저장할 res를 정의한다.
• input.length + 1만큼 loop를 돌려준다. (마지막 stack 더해주는 과정 + 1)

1. if el가 열린 괄호일 시

   • stack에 push한다.

2. else if el가 ')'일 시

   1. stack이 비어있거나,
      stack top이 '['일 시 ex: ([)
      → 틀린 괄호열이므로 실패

   2. stack top이 '('이면 ex: () 짝 괄호
      → stack의 이전 top을 pop한 후 2를 push

   3. stack top이 숫자일 시, 짝괄호인 '('가 나올 때까지 숫자들을 2 곱해주어야한다.
      → '('가 나올 때까지 pop하면서 숫자를 더해준다.
      → '('가 나오면 pop한 후 지금까지 더한 숫자 * 2를 push한다.

3. else if el가 ']'일 시
   #2와 동일한 로직이다.

4. else 모든 괄호를 다 순회했을 때

   1. [성공] stack에 숫자만 있을 시 괄호가 전부 짝이 맞음
   2. [실패] stack에 남은 '열린 괄호'가 있을시 짝이 안맞은 괄호가 있다는 의미이므로 실패

예제

위의 풀이로 예시 입력 (()[[]])([])의 답을 구해보면 다음과 같다.

전체 코드

const input = require('fs').readFileSync('/dev/stdin').toString();

class Stack {
  constructor() {
    this.arr = [];
  }
  push(item) {
    this.arr.push(item);
  }
  pop() {
    return this.arr.pop();
  }
  peek() {
    return this.arr[this.arr.length - 1];
  }
  isEmpty() {
     return this.arr.length === 0;
  }
}

const stack = new Stack();
let res = 0;

for (let i = 0; i <= input.length; i++) {
    const target = input[i];
    // target이 열린 괄호일 시
    if ((target === '(') || target === '[' ) {
        stack.push(target);
    }
    // target이 ')'일 시
    else if (target === ')') {
        // stack이 비어있거나, stack top이 '['이면 실패
        if (stack.isEmpty() || stack.peek() === '[') {
            res = 0;
            break;
        }
        // stack top이 '('일 시 2를 스택에 더해준다
        if (stack.peek() === '(') {
            // top '(' 없애기
            stack.pop();
            stack.push(2); // 2넣기
        }
        // stack top이 '숫자'일 시
        // stack에서 '('를 찾아서 곱셈
        else {
            let num = 0;
            while (stack.arr.length > 0) {
                let top = stack.pop();
                // '('일 시
                if (top === '(') {
                    stack.push(num * 2);
                    break;
                }
                // 숫자일 시
                else {
                    num += top;
                }
            }
        }
    }
    // target이 ']'일 시
    else if (target === ']') {
        // stack이 비어있거나, stack top이 '('이면 실패
        if (stack.isEmpty() || stack.peek() === '(') {
            res = 0;
            break;
        }
        // stack top이 '['일 시(맞는 짝) 3을 스택에 더해준다
        if (stack.peek() === '[') {
            // top '[' 없애기
            stack.pop();
            stack.push(3); // 3넣기
        }
        // stack top이 '숫자'일 시
        // stack에서 '['를 찾아서 곱셈
        else {
            let num = 0;
            while (stack.arr.length > 0) {
                let top = stack.pop();
                // '['일 시
                if (top === '[') {
                    stack.push(num * 3);
                    break;
                }
                // 숫자일 시
                else {
                    num += top;
                }
            }
        }
    }
  
  	// undefined일 때 (모든 괄호를 다 순회)
  	// - [성공] stack에 숫자만 있을 시 괄호가 전부 짝이 맞음
  	// - [실패] stack에 남은 괄호가 있을시 짝이 안맞은 괄호가 있다는 의미이므로 실패
    else {
        const isNumber = (curr) => (typeof curr === 'number');
        if (!stack.arr.every(isNumber)) {
            res = 0;
            break;
        }
        res = stack.arr.reduce((a,b) => (a+b), 0);
    }
}

console.log(res);