856. Score of Parentheses

💡풀이

var scoreOfParentheses = function (s) {
  let stack = [];
  let count;
  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') {
      stack.push('(');
    } else {
      if (stack[stack.length - 1] === '(') {
        stack.pop();
        stack.push(1);
      } else if (typeof stack[stack.length - 1] === 'number' && stack[stack.length - 2] === '(') {
        count = stack.pop();
        stack.pop();
        stack.push(2 * count);
      }
      // 내가 직접 구현 못한 부분
      while (
        stack.length &&
        typeof stack[stack.length - 1] === 'number' &&
        typeof stack[stack.length - 2] === 'number'
      ) {
        stack.push(stack.pop() + stack.pop());
      }
    }
  }
  return stack.pop();
};

// Optimal Solution(Stack) - 다른 사람의 풀이
const scoreOfParentheses = function (str) {
  // beginning score - 지정해주지 않으면 stack.pop을 할 때 오류가 날 것이다.
  let stack = [0];

  for (let s of str) {
    if (s === '(') {
      stack.push(0);
    } else {
      let top = stack.pop();
      let beforeTop = stack.pop();
      stack.push(beforeTop + Math.max(2 * top, 1));

      // Result of first else
      // [0, 1]

      // Result of second else
      // [0, 1, 1]

      // Result of third else
      // [0, 3]

      // Result of final else
      // [6]
    }
  }

  return stack.pop();
};

📝정리

Stack, Divide and Conquer, recursive 등 여러 방법이 있었다. 그 중 나는 Stack을 선택해서 문제를 풀었는데, 마지막 조건인

해당 조건에 대한 답을 결국 스스로 해결하지 못하고 Discussion을 참고했다. 맨 앞의 "stack.length가 있을때"라는 조건을 빠뜨린 것이 문제였다. 해당 while문의 코드를 보면 stack.pop()을 2번 하는데, 당연하게도 stack 배열 안에 값이 없다면 아래 코드를 실행시키지 못하는 것이 원인이었다. 어려운 문제였다.

문제 링크

https://leetcode.com/problems/score-of-parentheses/

LeetCode GitHub

https://github.com/tTab1204/LeetCode/tree/main/%EC%A3%BC%EC%98%81