20. Valid Parentheses

문제 링크: https://leetcode.com/problems/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.
3. Every close bracket has a corresponding open bracket of the same type.

'(', ')', '{', '}', '[' 및 ']' 문자만 포함하는 문자열 s가 주어지면 입력 문자열이 유효한지 확인합니다.
다음과 같은 경우 입력 문자열이 유효합니다.

1. 열린 브래킷은 동일한 유형의 브래킷으로 닫아야 합니다.
2. 열린 브래킷은 올바른 순서로 닫아야 합니다.
3. 모든 닫기 대괄호에는 동일한 유형의 해당 여는 대괄호가 있습니다.

 

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

 

Constraints:

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

Related Topics: String, Stack

---

문제풀이

 

괄호의 짝이 맞는 문자열인지 확인하는 함수를 작성한다.

1. push, pop을 이용해 빈 문자열에 열린 괄호 (, {, [를 넣는다(push).

2. 이후 문자열이 비었으면 짝이 될 괄호가 없는 상태이므로 false를 return한다.

2-1. sArr의 요소를 pop으로 뽑아내고 s[i]의 괄호를 비교해 (), {}, []의 짝이 맞지 않으면 false를 return 한다.

2-2. sArr의 길이가 0이면 true, 아니면 false를 return 한다.

 

객체를 활용해 key:value로 괄호 짝을 만들어 비교하면 더 간편하다.

//for 반복문으로 풀이
var isValid = function(s) {
    let sArr=[];
    for (let i=0;i<s.length;i++){
        if(s[i]==="(" || s[i]==="{" || s[i]==="["){
            sArr.push(s[i]);
        }else {
            if (sArr.length===0) return false;
            let sPop=sArr.pop();
            if(s[i]===")" && sPop!=="(" || s[i]==="]" && sPop!=="[" || s[i]==="}" && sPop!=="{"  ){
                return false;
            }
        }
    }
    return sArr.length===0;
    //빈 배열이면 true, 아니면 false
};

//객체 만들어서 배열 요소와 비교
//(이 경우, s를 split으로 각 괄호를 배열 요소로 만듦)
var isValid = function(s) {
    let valid = {'(':')','{':'}','[':']'};
    let check = s.split('').reduce(function(ac, cv) {      
        if (cv===valid[ac[ac.length-1]]) ac.pop();
        else ac.push(cv);
        return ac;    
    }, []);    
    return check.length === 0;
}