[Leetcode] 20. Valid Parentheses - JS

https://leetcode.com/problems/valid-parentheses/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
- (),{},[] 로 이루어진 문자열 s가 주어진다.
- 열린 괄호는 같은 종류의 괄호로 닫혀야 한다.
- 열린 괄호는 정확한 순서로 닫혀야한다.
- 모든 닫힌 괄호에는 동일한 유형의 열린 괄호가 있다.

제한조건
--------------------
- 1 <= s.length <= 10^4
- s는 (){}[]로 구성된다.

 

2. 접근 방법

접근방법
--------------------
stack 자료구조로 풀 수 있다.
stack은 후입선출 구조이다.

brakets에 열린 괄호에 맞는 닫힌 괄호 매핑
stack = [] 초기화
s를 순회하면서
    - 열린괄호면 stack에 push
    - 닫힌괄호면 stack의 pop한 요소가 같은 타입인지 비교하여 false 반환

stack이 비어있는지에 따라 true, false 반환

 

 

3. 코드

var isValid = function(s) {
    const brakets = {
        '(':')',
        '{':'}',
        '[':']'
    };
    const opens = Object.keys(brakets)
    const stack = [];

    for (let b of s) {
        if (opens.includes(b)) {
            stack.push(b)
        } else {
            let popped = stack.pop();
            if (b !== brakets[popped]) {
                return false
            }
        }
    }
    return stack.length === 0;
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(n)

 

해쉬맵을 사용하여 열린 괄호와 닫힌 괄호를 매핑해주었다.

닫힌 괄호가 등장하면, stack에서 최신에 넣은 열린 괄호를 빼내어 타입을 비교한다.

반복문이 종료되고 stack에 열린 괄호가 남아있으면 문제의 조건에 따라 같은 타입의 닫힌 괄호로 매핑되지 않았다는 뜻이므로

stack의 길이에 따라 true, false를 판단한다.