알고리즘 - Valid Parentheses

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. Opn brackets must be closed in the correct order.

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Example 4:

Input: s = "([)]"
Output: false

Example 5:

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

Constraints:

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

풀이

위 문제는 열림과 닫힘이 짝지어진 문자가 제대로 짝을 이루고 있는지를 리턴하는 문제이다. 괄호의 종류는 3종류이고 짝의 갯수는 맞더라도 열림과 닫힘의 위치가 정확하지 않으면 false 를 리턴 해야한다. 스택알고리즘을 활용하여 푸는방법으로 접근 할 수 있다.

코드

var isValid = function(s) {
    const left = []; // 열린 괄호를 저장말 배열
    const keyValue = { // 어떤 키와 밸류가 쌍을 이루는지 객체로 생성
        '(': ')',
        '[': ']',
        '{': '}',
    }
    for (let i = 0; i < s.length; i++) { // 문자열을 반복으로 돌림
        if (s[i] === '(' || s[i] === '[' || s[i] === '{') {
            // 열림태그에 해당하는 문자라면 left 배열에 추가
            left.push(s[i])
        } else if (keyValue[left.pop()] !== s[i]) {
            // 닫힘 태그에 해당하는 문자가 left 배열에 있는 열림태그와 쌍을 이루는지 확인
            return false
        }
    }
    return left.length > 0 ? 0: 1
};

샘플 4를 예로들면

Input: s = "([)]"
Output: false

1. s[0] 이 ( 에 해당하기때문에 left 에 push
2. s[1] 이 [ 에 해당하기때문에 left 에 push
3. s[2] 이 ) 에 해당하기때문에 마지막에 push 한 [ 를 가져와 keyValue 에서 찾으면 ] 즉 ] !== ) 이 같지 않기때문에 반복문 종료
4. left 에는 ['('] 가 아직 남아있기 때문에 0(false) 를 반환