LC - Valid Parentheses

goody·2021년 2월 23일
0

알고리즘

목록 보기
51/90

문제

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

예시

Input: s = "()"
Output: true

Input: s = "()[]{}"
Output: true

Input: s = "([)]"
Output: false


풀이

  • 문자열의 괄호 짝이 맞는지 검사하는 문제이다.
  • stack 자료구조를 활용하여 풀 수 있다.
  • 주어진 문자열을 앞쪽에서부터 검사하여 여는 괄호가 나오면 스택 배열에 push 한다.
  • 만약 닫는 괄호가 나왔는데 스택 배열의 맨 뒤 원소가 동일한 타입의 여는 괄호면 배열을 pop 한다.
  • 닫는 괄호가 스택 배열의 맨 뒤 원소와 동일한 타입이 아니라면 false를 반환한다.
  • 위 과정이 끝난 후 스택 배열이 비어있다면 true를, 그렇지 않다면 false를 반환한다.

코드

var isValid = function(s) {
    const arr = s.split("");
    const stack = [];
    let answer = true;
    
    if(arr.length === 1) return false;
    if(arr[0] === ")" || arr[0] === "]" || arr[0] === "}") return false;

    arr.forEach((el) => {
        if(el === "(" || el === "[" || el === "{") {
            stack.push(el);
            return;
        }
        
        if((el === ")" && stack[stack.length-1] === "(") || 
            (el === "]" && stack[stack.length-1] === "[") ||
            (el === "}" && stack[stack.length-1] === "{"))  {
                stack.pop();
            } else {
                answer = false;
            }
    });
    if(stack.length !== 0) answer = false;
    
    return answer;
 
};

0개의 댓글