[리트코드] 20. Valid Parentheses

안녕하세요. 개발조각입니다.😊

이번 문제는 알고리즘 문제 풀면 무조건 보는 문제인 것 같아요.

저도 이전에 프로그래머스에서 풀었었는데 또 보니까 반갑네요.

---

https://leetcode.com/problems/valid-parentheses/

Valid Parentheses - LeetCode

이번 문제는 쉬우니 빠르게 해결방안에 대해 설명하겠습니다.

 

해결방안

var isValid = function(s) {
    bracketMap = {
        '(':')',
        '{':'}',
        '[':']',
    };
    
    branckes = [];
    for(i of s){
        let len = branckes.length;
        if(bracketMap[i]) branckes.push(i);
        else{
            if(!len) return false;
            
            if(i === bracketMap[branckes[len-1]]) branckes.pop();
            else return false;
        }        
    }
    
    return branckes.length ? false : true;
};

 

간단하게 개념에 대해 설명을 하자면

branckes = []를 만들어

• '(', '{', '['일 경우 branckes에 넣어주고
• ')', '}', ']'일 경우 branckes의 마지막 원소가 ')', '}', ']'에 짝에 맞는 '(', '{', '['이면 제거를 해줍니다.
  • 짝이 안맞을 경우는 괄호의 짝이 안 맞는 경우이기 때문에 바로 false를 해줍니다.

 

왜 이렇게 했는지는 아래 이미지를 보시면 알 것 같습니다.

이렇게 진행을 하면 짝이 맞는 괄호이면

brancket = [ ] 이렇게 빈배열로 나오고 아닐 경우는 brancket배열 안에 원소가 있겠죠.

 

사실 위에있는 설명대로 코드를 짜면 통과는 되겠지만

효율을 위해 중간에 false가 될 수 있을 값을 미리 제거를 해줘야 됩니다.

예를 들어 아래와 같은 경우가 있습니다.

• ){}

이와같이 s[0]이 '(', '{', '['이 아닌 ')', '}', ']'경우에는 짝이 맞는 괄호인지 확인할 필요도 없겠죠.

 

---

bracketMap = {
    '(':')',
    '{':'}',
    '[':']',
};

문제가 단순하게 ()만 써서 맞는 괄호인지 찾는 문제면 안써도 되는데

이번 문제는 (), {}, []이렇게 3가지를 괄호의 짝이 맞는지 찾는 문제라 object형태로 나타냈습니다.

 

 

branckes = [];
for(i of s){
    let len = branckes.length;
    if(bracketMap[i]) branckes.push(i);
    else{
        if(!len) return false;

        if(i === bracketMap[branckes[len-1]]) branckes.pop();
        else return false;
    }        
}

for of문을 사용해서 문자열s의 각각의 괄호가 나오게 해주었고

 

 

if(bracketMap[i]) branckes.push(i);

이러한 조건문을 넣어

'(', '{', '[' 경우에 branckes배열에 넣어주었습니다.

 

 

else{
    if(!len) return false;

    if(i === bracketMap[branckes[len-1]]) branckes.pop();
    else return false;
}

else경우는 ')', '}', ']'일 경우겠죠

 

if(!len) return false;

이전에 '){}' 와 같은 테스트 케이스도 발생할 수 있기 때문에 이와 같은 조건을 넣어주었습니다.

 

if(i === bracketMap[branckes[len-1]]) branckes.pop();
else return false;

그리고 해당 괄호가 짝이 맞는지 확인하고 맞으면 branckes의 마지막 원소를 제거하고

아닐 경우 false를 리턴해주었습니다.

 

 

return branckes.length ? false : true;

마지막으로  s='{{{{{{{{'일 경우도 존재하니 이와같은 조건문을 써주었습니다.