[LeetCode] Valid Parentheses

문제링크

Valid Parentheses - LeetCode

 

주어진 괄호들이 올바른 괄호면 true, 아니면 false를 반환하는 문제이다.

접근 방법

stack개념을 사용하여 접근하였다. (First In Last Out)

1. 먼저 stack이 비었는데, 오른쪽 괄호가 나오면 false를 반환한다.

if(stack.length === 0 && rightBasket.includes(s[i])) return false;​

 

2. 왼쪽 괄호가 나오면 stack에 넣고, stack이 비어있지 않을 때 오른쪽 괄호가 나오면 비교를 진행한다.

// 왼쪽 괄호가 나올 경우
if(leftBasket.includes(s[i])) stack.push(s[i])
// 오른쪽 괄호가 나올 경우
else{
    if(leftBasket.indexOf(stack.pop()) === rightBasket.indexOf(s[i])){
        continue;
    }else return false;
}​

({[]}) 같은 괄호가 있다면 stack에는 [ '(', '{', '[' ] 순으로 들어가고,
pop을 할 경우 이처럼 [ '[', '{', '(' ] 역순으로 나와서 오른쪽 괄호와 순서에 맞게 비교할 수 있다.

3. 조건문이 끝났는데 stack이 비어있지 않다면 false, 비어 있다면 true를 반환한다. 

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

 

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    const leftBasket = ["(", "[", "{"];
    const rightBasket = [")", "]", "}"];
    const stack = [];
    
    for(let i = 0; i < s.length; i++){
        // stack이 비었는데 오른쪽 괄호가 나오면 false
        if(stack.length === 0 && rightBasket.includes(s[i])) return false;

        // 왼쪽 괄호가 열리면 stack에 넣고 오른쪽 괄호가 나오면 stack과 비교
        // 왼쪽 괄호가 나오면 stack에 추가
        if(leftBasket.includes(s[i])) stack.push(s[i])
        // 오른쪽 괄호가 나오면 stack을 빼고 index번호 비교
        else{
            if(leftBasket.indexOf(stack.pop()) === rightBasket.indexOf(s[i])){
                continue;
            }else return false;
        }
    }
    
    return stack.length === 0 ? true : false;
};