알고리즘/리트코드

856. Score of Parentheses

창고 2021. 7. 14. 20:59

https://leetcode.com/problems/score-of-parentheses/discuss/141777/C%2B%2BJavaPython-O(1)-Space 

 

[C++/Java/Python] O(1) Space - LeetCode Discuss

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

내 풀이는 의미가 없다. lee215씨의 코드를 보자.

 

https://leetcode.com/problems/score-of-parentheses/discuss/141777/C%2B%2BJavaPython-O(1)-Space 

 

[C++/Java/Python] O(1) Space - LeetCode Discuss

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

잘 이해가 안간다. 실제로 케이스를 넣고 하나하나 따라가보니 문제에서 요구하는 해답을 구하는건 알겠지만, 어떻게 이런 생각을 했는지는 잘 모르겠다.

 

function scoreOfParentheses(s) {
    let stack = [];
    let cur = 0;
    for(let i = 0; i < s.length; i++) {
        if (s[i] == '(') {
            stack.push(cur);
            cur = 0;
        } else {
            cur = stack.pop() + Math.max(cur * 2, 1);
        }
    }
    return cur;
}