문제 괄호들로 이루어진 string을 입력받아서, 괄호들의 순서가 올바른지 판단해주는 함수를 완성해주세요. 괄호들은 ()와 {}와 [], 이렇게 총 3가지 종류가 있습니다. 괄호들은 자기와 짝이 맞는 괄호를 만나야만 합니다.
다음의 예를 봐주세요.
1 2 3 4 5 6 7 8 "(){}[]" => True"([{}])" => True"(}" => False"[(])" => False"[({})](]" => False@param {string} braces @return {boolean}
문제 이해 괄호들이 이루어진 string을 입력받아서, 그 소, 중, 대괄호가 모두 유효한지 검사하는 알고리즘을 짜는 문제이다.
해결 방법1 여러가지 괄호 string의 경우를 생각 해보고, 귀납적으로 해결방법을 구상했다.
그 중 괄호가 유효할 수 있는 최소한의 조건을 추렸다.
“(){}[]” => True, 전체 괄호 string의 길이가 짝수이어야 한다.
“(}” => False, 특정괄호의 개수와 그 짝 괄호의 개수가 같아야 한다.
“[(])” => False, 짝괄호 사이의 공간 값이 짝수이어야 한다.
코드 구현1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 function validBraces (braces ) var checking; var arrS1 = []; var arrS2 = []; var arrM1 = []; var arrM2 = []; var arrL1 = []; var arrL2 = []; if (braces.length % 2 === 0 ) { function check (brace, saveArr ) while (position1 !== -1 ) { var position1 = braces.indexOf(brace, position1 + 1 ); if (position1 !== -1 ) saveArr.push(position1); } } check("(" , arrS1); check(")" , arrS2); check("{" , arrM1); check("}" , arrM2); check("[" , arrL1); check("]" , arrL2); function checkArrLength (array1, array2 ) if (array1.length === array2.length) { return 1 ; } else { return 0 ; } } var cAlS = checkArrLength(arrS1, arrS2); var cAlM = checkArrLength(arrM1, arrM2); var cAlL = checkArrLength(arrL1, arrL2); function difference (Arr1, Arr2 ) if (Arr1.length === 0 ) { checking = 0 ; return checking; } else { for (var i = 0 ; i < Arr1.length; i++) { if ((Arr2[i] - Arr1[i]) % 2 === 1 ) { checking = 0 ; return checking; } else { checking = -1 ; return checking; } } } } var S = difference(arrS1, arrS2); var M = difference(arrM1, arrM2); var L = difference(arrL1, arrL2); if (S + M + L === 0 && cAlS * cAlM * cAlL === 1 ) { return true ; } else return false ; } return false ; }
결과 분석1 1 2 3 4 5 validBraces("}}]]))}])" ); validBraces("())({}}{()][][" ); validBraces("{}{[{}}]({})[]" ); validBraces("{}{[{}}]({})[]" ); validBraces("[(])" );
통과1 해결 방법 2 - stack 자료구조 이용, Last-In First-Out(마지막으로 들어가서 먼저 나온다)
str(괄호들로 이루어진 문자열)을 왼쪽부터 오른쪽까지 탐색한다.
왼쪽이 닫힌 ‘( or [ or {‘ 괄호를 만나면 배열에 쌓는다.
오른쪽이 닫힌 ‘) or ] or }’ 괄호를 만나면 배열의 마지막 요소와 매칭되는지 비교한다.
매칭이 되면 배열의 마지막 요소를 지운다. 그렇지 않다면, 탐색을 계속한다.
탐색이 끝난 후, 배열에 남은 요소가 있다면 ‘false’를, 남은 요소가 없다면 ‘true’를 return 한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 function matchingBrackets (str ) var checkArr = []; for (var i = 0 ; i < str.length; i++) { if (str[i] === "(" || str[i] === "[" || str[i] === "{" ) { checkArr.push(str[i]); } else { if ( (checkArr[checkArr.length - 1 ] === "(" && str[i] === ")" ) || (checkArr[checkArr.length - 1 ] === "[" && str[i] === "]" ) || (checkArr[checkArr.length - 1 ] === "{" && str[i] === "}" ) ) { checkArr.pop(); } } } if (checkArr.length === 0 ) { return true ; } else { return false ; } } matchingBrackets("(){{()[]}}[(){}]" ); matchingBrackets("[(){[{}]}([)[]]]" );