[Algorithm] 올바른 괄호

문제 설명

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

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

제한사항

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

입출력 예

"()()"	| true
"(())()"| true
")()(" | false
"(()(" | false

문제 해결

1. (로 시작하면 카운트에 1을 더하고 카운트가 0인 상태로 )이면 false, )가 등장하면 카운트에 1을 뺀다. 최종 카운트가 0이면 true 혹은 false를 반환한다.

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

    return count === 0;
}

2. stack으로 풀이했다. 두 경우 시간복잡도는 O(n)이지만 테스트를 돌려본 결과 stack 풀이는 시간초과인 케이스가 존재한다.

function solution(s) {
    const stack = [];

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

    return stack.length === 0;
}