[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 3:

Input: s = "(]"
Output: false

❗ 내 풀이

해당 문제를 푸는데 생각보다 오래 걸렸다.
풀고 난 뒤 다른 사람의 코드를 보니 아 이거 스택 문제이구나를 그제야 깨달았다ㅠㅠ
1. 괄호의 타입이 같으면 삭제해서 계속 비교하려고 하니 순서도 중요하여 중첩되었을 때 원하는 결과를 도출하지 못하였다.
2. 괄호 반대로 문자열을 만든 다음에 revese 하면 되지 않을까? 중첩되지 않은 괄호와 중첩된 괄호가 겹치게 될 경우 문제가 발생하였다. 
3. 결국 temp에 담아서 temp의 마지막 문자로 비교하여 같으면 temp 내 문자 삭제 / 다르면 false를 리턴하였다.

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    const brackets = {
        '(' : ')',
        '{' : '}',
        '[' : ']'
    };
   let temp = '';
    
    for(let i = 0; i < s.length ; i++) {
        if(brackets[s[i]]) {
            temp +=  brackets[s[i]];
        } else {
            if(temp && temp.charAt(temp.length - 1) == s[i]) {
                temp = temp.slice(0, -1);
            } else {
                return false;
            }
        }
    } 
    return temp.length == 0 ? true : false;
};

Runtime: 60 ms
Memory Usage: 42.5 MB

❗ 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
    
};

변수명들이 길어서 조금 헷갈렸지만, 스택으로 이루어져 있다는 것을 확인할 수 있다.

나도 스택을 써서 넣고 비교해야 하는데 문자열로 넣어주고 자르는 방식이라니...😂

 

또 다른 점은 return 부분이 다르다. 나는 삼항 함수를 써서 값을 리턴하였는데 그냥 조건으로 return 할 수 있다!

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

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    
    let map = {
        '[' : ']',
        '{' : '}',
        '(' : ')',    
    }
    
    let stack = [];
    let pushChars = Object.keys(map);
    for(let i=0; i< s.length; i++){
        let curr = s.charAt(i);
        if(curr in map){
            stack.push(curr);
        }else{
            let peek = stack[stack.length - 1];
            
            if(curr == map[peek]) stack.pop();
            else return false;
        }
    }
    
    return stack.length == 0;
    
};

마찬가지로 스택 방식으로 구현하였다.

 

if(curr in map)이 여전히 헷갈려서 다시 정리함! if(값 in map)이면 해당 값이 map의 키!!!에 있는 지를 확인하는 in함수이다.

 

참고로 pushChars 변수는 쓰이지 않았지만, Object.keys() 메서드는 객체의 키 값을 배열로 반환하는 메서드이다.

 

❗ 또 다른 답변과 비교

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let stack = [];
    
    for(let i=0;i<s.length;i++){
        if(s[i] === ']'){
            if(stack.pop() !== '[')
                return false;
        }
        else if(s[i] === ')'){
            if(stack.pop() !== '(')
                return false;
        }
        else if(s[i] === '}'){
            if(stack.pop() !== '{')
                return false;
        }
        else
            stack.push(s[i]);
    }
    
    return stack.length === 0;
};

코드가 깔끔해 보여서 복붙 하였다.

해당 코드를 이용하여 다시 코드를 짜도 괜찮겠다는 생각을 가지게 되었다.

 

💡 개선방안 적용 후 내 풀이

이 문제는 스택과 관련된 문제이다.

스택 관련 함수인 pop, push 메서드를 적극 활용하자.

/**
 * @param {string} s
 * @return {boolean}
 */
 var isValid = function(s) {
    const brackets = {
        '(' : ')',
        '{' : '}',
        '[' : ']'
    };
    let stack = [];
    
    for(let i = 0; i < s.length ; i++) {
        if(brackets[s[i]]) {
            stack.push(brackets[s[i]]);
        } else {
            if(stack.pop() !== s[i]) {
                return false;
            }
        }
    } 
    return stack.length == 0;
};

Runtime: 83 ms
Memory Usage: 42.1 MB

 

🚩 Detail

• 날짜 : 2022.03.16
• 난이도 : Easy
• 제목 : Valid Parentheses
• URL : https://leetcode.com/problems/valid-parentheses/