LeetCode의 올바른 괄호문제 풀어보기

bookmark

이번 글에서는 LeetCode에서 Valid Parentheses 문제를 풀어보겠다

Stack

• stack은 마지막에 들어간 요소가 가장 먼저 나온다는 개념을 가진 선형 자료 구조이다.

코드

function isValid(s: string): boolean {
    let stack = [];

    const pairBrackets = new Map();
    pairBrackets.set("(",")");
    pairBrackets.set("{","}");
    pairBrackets.set("[","]");
    
    for(const x of s) {
        if(pairBrackets.has(x)) {
            stack.push(x);
        }
        else {
            const lastOne = stack.pop();
            if(pairBrackets.get(lastOne) !== x) return false;
        }
    } 
    
    return stack.length === 0;
};

1. 객체나 map을 사용하여 각 괄호에 맞는 짝들을 묶어준다.
2. 문자열을 순회하여 만약 “(” 와 같은 열린 괄호라면 stack 배열에 넣어준다
3. “)” 와 같은 닫힌 괄호라면 가장 위에 있는 stack에 들어가있는 원소를 빼어서 그것의 value값과 현재 문자열이 일치하지 않으면 false를 해준다.
4. stack이 다 비워져있으면 정상적인 괄호값이므로 true를 리턴해준다