[LeetCode] Valid Parentheses (JS)

LeetCode | Valid Parentheses

문제

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

An input string is valid if:

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

입출력 예
Input: s = "([)]"
Output: false

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

접근

프로그래머스에서도 비슷한 문제를 본 적 있는 것 같습니다... 물론 풀진 않았었지만ㅎ

이 문제는 주어지는 문자열의 괄호가 올바른 순서대로 열리고 닫히고 있는지를 확인하여 return하는 문제입니다.

제가 접근한 방법은 모든 문자열을 검사하여 열린 괄호 바로 뒤 괄호가 동일한 괄호라면 차례대로 지워나가는 방법입니다.

예를 들어 "[]{({})}{}"같은 문자열이 주어졌다면,
"[]{({})}{}" => "{()}" => "{}" => ""
이와 같이 문자열이 줄어들 것 입니다.

이 알고리즘을 수행하기 위해 재귀를 사용합니다. 재귀 안의 로직은 다음과 같습니다.

1. 재귀의 탈출 조건은 들어오는 문자열의 길이가 0이면 true를 리턴합니다.
2. 만약 주어진 문자열을 모두 반복했는데 지워지지 않고 처음 길이와 같다면 순서가 제대로 이루어져 있지 않다는 것을 의미하므로 false 입니다.
3. 길이가 다르다면 다시 지워진 그 문자열을 가지고 다시 재귀를 돌립니다.

풀이

    s = s.split('');
    
    let recursion = (string) => {
        if(!string.length){
            return true;
        } 
        
        const sL = string.length;
        for(let i = sL - 1 ; i > 0; i--){
            if(string[i] === ")" && string[i - 1] === "("){
                string.splice(i - 1, 2);
                --i;
            }else if(string[i] === "]" && string[i - 1] === "["){
                string.splice(i - 1, 2);
                --i;
            }else if(string[i] === "}" && string[i - 1] === "{"){
                string.splice(i - 1, 2);
                --i;
            }
        }
        if(sL !== string.length){
            return recursion(string)
        }else{
            return false;
        }
    }
    
    return recursion(s);    
};

다른 방법

leetcode 솔루션을 통해 방법을 확인했습니다... 저번에 풀었던 문제와 비슷한 방법을 사용해서 풀이됐습니다.

문제를 접근하기 전에 비슷한 유형의 문제를 풀었던 적 있는지 생각해봤지만 방법이 떠오르지 않았는데ㅜㅜ

이 방법은 stack을 활용하여 반복문을 사용합니다.

1. 만약 "(", "{", "[" 가 현재 값이라면 stack에 push합니다.
2. 만약 현재 값이 ")", "}", "]"인데 stack의 마지막값이 현재 값과 버킷 종류가 일치하지 않는 열림 버킷이라면 false를 return합니다.
3. 일치하는 열림 버킷이라면 stack에서 pop합니다.
4. 모든 문자열을 반복을 통해 stack에 push&pop 했는데 남아있는 값이 존재한다면 false, 없다면 true입니다.

예를 들어 "({({})}"같은 문자열이 주어졌다면, 스택의 값은

["(", "{", "(", "{"] 이후 pop을 3번 진행하여 결국 stack은 ["("]이 됩니다. => false를 return합니다.

var isValid = function(s) {
    let stack = [];
    
    for(let i = 0; i < s.length; i++){
        if(s[i] === "(" || s[i] === "{"|| s[i] === "["){
            stack.push(s[i]);
        }else if(s[i] === ")"){
            if(stack[stack.length - 1] !== "(") return false;
            else stack.pop();
        }else if(s[i] === "}"){
            if(stack[stack.length - 1] !== "{") return false;
            else stack.pop();
        }else if(s[i] === "]"){
            if(stack[stack.length - 1] !== "[") return false;
            else stack.pop();
        }
    }
    
    return stack.length === 0 ? true : false;
    
};