올바른 괄호(Javascript)

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

• "()()" 또는 "(())()" 는 올바른 괄호입니다.
• ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

제한사항

• 문자열 s의 길이 : 100,000 이하의 자연수
• 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

입출력 예

s	answer
"()()"	true
"(())()"	true
")()("	false
"(()("	false

입출력 예 설명

입출력 예 #1,2,3,4
문제의 예시와 같습니다.

나의 풀이

function solution(s){
    let sum = 0;
  	if(s[0] === ')')
      return false;
    for(let i = 0; i < s.length; i++){
        s[i] === '(' ? sum += 1 : sum -= 1
        if(sum < 0)
            return false;
    }
    return sum === 0 ? true : false;
}

효율성 부분에서 고생을 많이 한 문제이다. 처음에는 스택/큐 문제니까 배열에 push()와 pop()을 활용해서 풀었는데, 시간이 너무 오래 걸리고 중간에 리턴할 지점도 찾기가 어려웠다. 그래서 만약 (라면 1을 더하고, )을 빼준 뒤 그 합이 0보다 작으면((가 하나 더 많아지면) 바로 리턴을 해줬다. 이렇게 해도 시간 초과가 나서 첫번째 값이 )라면 바로 리턴하는 코드를 넣어주니까 효율성 테스트를 통과할 수 있었다.

실패한 풀이

function solution(s){
    let arr = [];
    for(let v of [...s]){
       if(arr[arr.length-1] === '(' && v === ')'){
           arr.pop();
       }
        else
            arr.push(v);
    }
    return arr.length === 0;
}

function solution(s){
    let sum = 0;
    for(let i = 0; i < s.length; i++){
        s[i] === '(' ? sum += 1 : sum -= 1
        if(sum < 0)
            return false;
    }
    return sum === 0 ? true : false;
}