[백준] 2504번: 괄호의 값 (Node.js)

백준에서 2504번: 괄호의 값 (난이도: Silver I) 확인하기

 

1. 문제

 

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-1. 입력

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

 

1-2. 출력

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

 

---

 

2. 풀이 

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

const getPoints = parens => {
  const stack = [];

  for (let i = 0; i < parens.length; i++) {
    if ((parens[i] === '(' && parens[i + 1] === ')') || (parens[i] === '[' && parens[i + 1] === ']')) {
      stack.push(parens[i] === '(' ? 2 : 3);
      i += 1;
      continue;
    }

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

    if (parens[i] === ']' || parens[i] === ')') {
      const MAGIC_NUMBER = parens[i] === ')' ? 2 : 3;
      let accumulated = 0;

      while (typeof stack.at(-1) === 'number') {
        accumulated += stack.pop();

        if (!stack.length) return 0;
      }

      if ((parens[i] === ')' && stack.at(-1) === '(') || (parens[i] === ']' && stack.at(-1) === '[')) stack.pop();
      else return 0;

      stack.push(accumulated * MAGIC_NUMBER);
    }
  }

  for (let i = 0; i < stack.length; i++) {
    if (typeof stack[i] === 'string') return 0;
  }

  return stack.reduce((cur, acc) => cur + acc);
};

console.log(getPoints(input));

 

2-1. 접근 방식 

 

여는 괄호와 닫는 괄호로 구성되어 있는 입력 값을 순회하며 다음 세 가지 케이스를 확인했다. 

 

1. 여는 괄호와 닫는 괄호가 인접 쌍인 경우, 즉 중간에 아무 것도 포함되지 않은 쌍이어서 즉시 점수로 계산될 수 있을 때는 stack에 숫자를 push 했다.
2. 인접 쌍이 아닌데 여는 괄호가 나왔을 경우, 즉 중간에 다른 값이 포함되어 있을 수도 있는 경우에는 여는 괄호 그대로 push 했다.  
3. 닫는 괄호인 경우에는 stack의 최상단 값이 숫자 타입인지 확인한다. 숫자 타입인 경우 문자열 타입의 값이, 즉 여는 괄호, stack의 최상단에 위치할 때까지 stack에서 숫자 타입 값을 pop하고 accumulated 변수에 누적해두었다. 문자열 값이 stack 최상단에 위치하게 되면, 현재 값과 쌍이 되는지 확인하고 누적된 점수를 계산해 stack에 다시 push했다.

이후 완성된 stack을 다시 한번 순회하며 문자열 값을 포함하고 있는 경우 0을 반환했고, 문자열 값이 포함되지 않은 경우 stack에 저장되어 있는 값을 모두 더해 반환했다. 

 

2-2. 회고

 

• TC를 보면서 손으로 스택을 그려가면서 푸니까 로직을 구현하는 과정이 훨씬 수월했다. 
• ...라고 말한 것 치고는 문제를 4번이나 틀렸는데, 마지막에 문자열 값이 stack에 포함되어 있는지 확인하지 않았기 때문이다. 입력 값으로 '(((((((' 를 넣어서 해보면 왜 그런지 알 수 있다.