[알고리즘/자바스크립트] 괄호 짝 찾기 (Valid Braces)

-해당 문제는 codewars사이트의 level6 문제입니다. (1~8단계 중 8단계가 가장 쉬운 레벨)-

 

[문제] 괄호들로 이루어진 string을 입력받아서, 괄호들의 순서가 올바른지 판단해주는 함수를 완성해주세요!

괄호들은 ()와 {}와 [], 이렇게 총 3가지 종류가 있습니다.

괄호들은 자기와 짝이 맞는 괄호를 만나야만 합니다.

다음의 예를 봐주세요,

validBraces("(){}[]") // => True
validBraces("([{}])") // => True
validBraces("(}") // => False
validBraces("[(])") // => False
validBraces("[({})](]") // => False

* @param {string} braces

* @return {boolean}

 

---

 

이 문제를 보자마자 지난번에 풀었던 "반대방향 제거하기" 문제가 떠올랐다.

 

https://im-developer.tistory.com/56?category=819313

[알고리즘/자바스크립트] 배열에서 반대 방향 제거하기 (Directions Reduction)

 

두 문제의 공통점은 어떤 특정한 짝을 만나면 두 개를 묶어서 판단해야한다는 점이다.

지난번 문제에서는 "North"와 "South" / "East"와 "West" 이렇게 묶어서 배열에서 제거를 했어야했다.

 

 

이번 문제도 지난번에 풀었던 문제처럼 () {} [] 이렇게 괄호를 묶어서 제거하면 된다고 생각했다.

코드는 다음과 같다.

 

function validBraces (braces) {
    var bList = { "(" : ")", "{" : "}", "[" : "]" }

    var verify = braces.split('').reduce(function(ac, cv) {
        if (cv === bList[ac[ac.length - 1]]) {
            ac.pop();
        } else {
            ac.push(cv);
        }
        return ac;
    }, []);
    return verify.length === 0;
}

 

• 일단 빈 배열, verify를 만든다.
• 괄호들의 모음을 객체(bList)로 만드는데, (, {, [를 키값으로 하고 value값은 ), }, ]로 한다.
• 괄호 string은 split()함수를 사용하여 배열로 만들어서 iterate한다.
• 반복문에서 괄호 배열의 현재 요소(cv)가 괄호 객체(bList)에 키값으로 존재한다면 빈 배열 verify 맨 뒤에 값을 넣는다.
• 만약에 키값으로 존재하지 않는 경우에 verify 배열의 맨 마지막 요소의 값을 key로 하여 bList의 value를 찾는다. 현재 요소가 이 value값과 일치하면 괄호의 짝이 맞는다는 얘기이므로 verify 배열에서 마지막 요소를 삭제한다.
• 현재 요소와 위에서 찾은 value값이 일치하지 않는다면 배열 맨 뒤에 값을 넣는다.
• 괄호의 짝이 모두 맞는 경우에는 반복문이 끝난 후 verify가 빈 배열이 된다. → return true
• 반대로 괄호의 짝이 하나라도 안맞는다면 verify에 짝이 안맞는 괄호가 들어있게 된다. → return false