Programmers.js - 올바른 괄호

이거 책에 있던 문제인데.
재귀로 한번 풀어봤음

효율성 테스트에서 런타임 에러가 나와가지고 이유가 뭘까 생각해봤음
문자열이 매우 길어서, 재귀가 너무 깊어져 시간 복잡도가 기하 급수적으로 늘어났다면 확실히 시간이 오래 걸릴거 같음

그래서 그제 책에서 stack으로 풀어봤던걸 떠올려서 다시 풀어봄

function solution(s){
    const stack = []
     if(s[0] === ')'){
            return false
        }
    for(let i = 0; i < s.length; i++){
        if(s[i] === '('){
            stack.push(s[i])
        } else if(s[i] === ')'){
            if(stack.length === 0){
                return false
            }
            stack.pop()
        }
    }
        return stack.length === 0;
}

효율성 테스트 계속 실패하길레 뭐가 문젠지 고민하다 console.log() 안지워서 그랬었음 허허;

아래는 그리디 알고리즘으로 푼거
나는 처음에 ')'만 걸러줄 생각을 했지 이렇게 하는건 생각도못해봄 식견이 늘었다..

function solution(s){
    let cum = 0
    for (let paren of s) {
        cum += paren === '('? 1: -1
        if(cum < 0) {
            return false
        }
    }
    return cum === 0? true: false;
}