자료구조 stack 개념 활용한 알고리즘 문제: balancedBrakets

문제

문자열을 입력받아 문자열 내의 모든 괄호의 짝이 맞는지 여부를 리턴해야 합니다. 다음 단계에 맞춰 함수를 작성해 보세요

• 괄호의 종류를 단 한가지로 한정합니다.
• 괄호의 종류를 늘려 모든 종류의 괄호에도 작동하도록 합니다.
• 괄호를 제외한 문자열이 포함된 경우에도 작동하도록 합니다.

<주의사항>
괄호의 종류는 (, )만 고려합니다.
괄호는 먼저 열리고((), 열린만큼만 닫혀야()) 합니다.
빈 문자열을 입력받은 경우, true를 리턴해야 합니다.
모든 종류의 괄호((, ), {, }, [, ])가 포함된 문자열을 입력빋아 모든 괄호의 짝이 맞는지 여부를 리턴해 보세요.

수도코드

가장 최근에 나타났던 괄호와 지금 새로 나타난 괄호의 짝이 맞는지를 봐야하므로, 뭔가 최근의 값을 다루는 경우에는 stack(배열형태)을 이용한다.

str[i]가 opener이면 stack 에 넣고

str[i]가 closer이면

1. stack에서 마지막 요소를 제거하고 이를 top이라고 한다.

2. top과 str[i]가 짝이 맞으면 true를 반환한다.

 

즉, 닫힘괄호(), }, ])가 들어왔을 때, stack에 마지막으로 들어있는 값을 확인한다. 마지막 값이 pair((, {, [)이면 pop한다.  아닌 경우는 모두 push한다. stack에 남은 원소 값이 없는 경우 true, 원소가 남아있으면 false를 반환한다.

stack에 쌓이는 것은 opener이고, str[i]가 closer일 때에는 이 closer가 stack에 가장 마지막에 넣은 요소와 짝이 맞는지 확인한다.

결과적으로 stack에 아무것도 남지 않게 되면 결과는 true이다.

코드로 나타내보면

const balancedBrackets = function (str) {
  
  const array = str.split("");
  //일단 배열형태로 만들고

  let stack = [];
  for (let item of array) {//요소를 훑으면서
    if (item === "{" || item === "[" || item === "(") { //opener라면
      stack.push(item); //stack에 넣고
    } else { //closer라면
      if (stack.length === 0) {
        //ope
        return false;
      }
      if (item === "}" && stack[stack.length - 1] === "{") { 
        //{} 쌍이 맞는지 확인
        stack.pop();
      } else if (item === "]" && stack[stack.length - 1] === "[") { 
        //[] 쌍이 맞는지 확인
        stack.pop();
      } else if (item === ")" && stack[stack.length - 1] === "(") {
        //() 쌍이 맞는지 확인
        stack.pop();
      } else if(item === "}" || item === "]" || item === ")") { 
        //쌍이 안 맞는 경우엔 stack에 넣는다
        stack.push(item);
      }
    }
  }

  return stack.length > 0 ? false : true;

};