[Reet code] 20. Valid Parentheses

Intuition

SWEA 나 프로그래머스, 백준 등등에서 많이 본 스택의 대표문제. 올바른 괄호인지 검증하는 문제였다.

Approach

• 여는 괄호가 나오면 스택 push
• 닫는 괄호가 나왔을 때, 스택의 tail 이 일치하면 pop 그렇지 않으면 false
• 끝까지 순회하고 stack 이 비었으면(짝이 다 맞았으면) true, 그렇지 않으면 false
• 계산을 그나마 쉽게 하려고 여닫는 괄호를 객체로 만들어서 더한게 0이 되는지 확인했다.

Complexity

• Time complexity: O(N)

Code

function isValid(s: string): boolean {
    const open = {"(": 1, "{": 2, "[": 3};
    const close = {")": -1, "}": -2, "]": -3};

    const stack = []
    for (let i = 0; i < s.length; i++) {
        if (stack.length === 0) {
            stack.push(open[s[i]])
            continue
        }
        if (open[s[i]]) {
            stack.push(open[s[i]])
        } else if (stack[stack.length - 1] + close[s[i]] === 0 ) {
            stack.pop()
        } else {
            return false
        }
    }

    return stack.length === 0 ? true : false
};