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
Author And Source
이 문제에 관하여(856. Score of Parentheses), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ken1204/856.-Score-of-Parentheses저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)