[leetCode] 20. Valid Parentheses (Easy) 풀이

❓ 문제

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.

'(', ')', '{', '}', '[' 그리고 ']' 로 이루어진 주어진 문자열이 유효한지 알아내세요.

문자열이 유효한 경우:

1. 열린 괄호가 닫힌 괄호와 모양이 일치해야합니다.
2. 열리 괄호는 올바를 순서로 닫혀야합니다.

Example 1

Input: s = "()"
Output: true

Example 2

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

Example 2

Input: s = "(]"
Output: false

Constraints:

1 <= s.length <= 104
s consists of parentheses only '()[]{}'.

❗ 내 답변

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    const strArr = s.split('');
    const arr = [];
    for (let i = 0; i < strArr.length; i++) {
         switch(strArr[i]) {
            case '(':
                arr.push(')');
                break;
            case '{':
                arr.push("}");
                break;
            case '[':
                arr.push("]");
                break;
            default: 
                if (strArr[i] !== arr.pop())
                    return false;
        }
    }

    return arr.length === 0;
}

Runtime: 67 ms
Memory Usage: 42.5 MB

 

이번 문제는 내게 너무 어려워 다른 분들의 문제를 보고 풀었다. ^.T (풀다보면 점점 늘겠지..?)

const validInfo = {
    '(': ')',
    '[': ']',
    '{': '}'
}

처음엔 위와 같은 객체를 사용해서 열린 괄호에 매칭되는 닫힌 괄호를 indexOf 또는 lastIndexOf 로 찾아 구해보려고 했었다.
index를 찾으면 splice 따위로 문자열을 담은 배열을 잘라내어 다시 반복 돌리려 했었지만,
같은 열린 괄호가 여러개 있는 상황이나, 배열이 닫히는 위치가 일정하지 않다는 점을 생각하지 못해 실패했다.

결국 힌트를 얻고 푼 문제를 풀었다.
switch를 통해 열린 괄호에 대한 닫힌 괄호를 배열에 담고,
닫힌 괄호일 때는 직전에 배열에 담은(pop()) 문자열과 같은지 비교하고 그렇지 않을 경우(같은 모양의 괄호로 닫히지 않은 경우) false를 반환 시킨다.
정상적으로 push와 pop()을 반복했다면 담았던 배열을 모두 비워져 있을 것이기 때문에,
마지막으로 arr.length === 0;를 반환 시켰다.

❗ Runtime이 가장 빨랐던 답변과 비교

const closeBracketPairs = {
    ')': '(',
    '}': '{',
    ']': '['
 }

var isValid = function(s) {

    const openBracketsStack = []

    for(let i = 0; i < s.length; i++) {

        const closeBracketPair = closeBracketPairs[s[i]]
        const isCloseBracket = closeBracketPair !== undefined

        if(isCloseBracket) {
            const lastOpenBracket = openBracketsStack.pop()
            const isCloseBracketValid = lastOpenBracket === closeBracketPair

            if(!isCloseBracketValid) {
                return false
            }
        } else {
            openBracketsStack.push(s[i])
        }

    }

    return openBracketsStack.length === 0

};

Runtime: 56 ms
Memory Usage: 42.1 MB

 

이 답변은 내가 처음 시도했었던 방식으로 진행됐다.
서로 매칭되는 괄호 정보를 가지고 있는 객체를 선언하며 시작된다.

현재 문자가 닫힌 괄호가 아니라면(열린 괄호라면) 여분의 배열에 해당 문자를 담아둔다.
닫힌 괄호라면 배열에서 가장 마지막에 담은 문자를 가져온다. (pop())

배열엔 항상 열린 괄호만 담길 것이기 때문에 가장 마지막에 담긴 문자는 열린 괄호 일 것이고,
이 열린 괄호와 현재 괄호(닫힌 괄호)와 매칭되는 열린 괄호를 비교한다.

일치한다면 맞는 것이니 다음 반복으로 넘어가고,
일치하지 않다면 false를 반환한다.

❗ Memory 사용이 가장 적었던 답변과 비교

/**
 * @param {string} s
 * @return {boolean}
 */

var isValid = function (s) {
    let map = new Map();

    map.set('{', '}');
    map.set('(', ')');
    map.set('[', ']');

    let b = [];
    for (let i = 0; i < s.length; i++) {
        if (map.has(s.charAt(i))) {
            b.push(s.charAt(i));
        }
        else {
            let pop = b.pop();
            if (map.get(pop) !== s.charAt(i)) {
                return false;
            }
        }
    }

    return b.length === 0;
};

Runtime: 72 ms
Memory Usage: 41.6 MB

이 답변은 객체가 아닌 new Map()을 활용했다.
서로 매칭되는 괄호에 대한 정보를 Map에 담고 반복을 돌면서
위 답변들과 같이 여분의 배열(b)에 push, pop을 통해
참, 거짓을 판단한다.

💡 개선 방안

switch든 객체든 Map()이든...
어떤 매칭되는 문자를 찾고자할 때는 배열을 적극 활용하여 push, pop 하자!