Algorithm 22 : balancedBrackets

설명

문자열을 입력받아 문자열 내의 모든 괄호의 짝이 맞는지 여부를 리턴해야 합니다.

다음 단계에 맞춰 함수를 작성해 보세요
괄호의 종류를 단 한가지로 한정합니다.
괄호의 종류를 늘려 모든 종류의 괄호에도 작동하도록 합니다.
괄호를 제외한 문자열이 포함된 경우에도 작동하도록 합니다.

예시

let output = balancedBrackets('(');
console.log(output); // // -> false

output = balancedBrackets('()');
console.log(output); // --> true

생각

'('가 나온 후 ')'가 나오는 순서이기 때문에 먼저 '(' 요소를 stack에 담고, ')'가 나오면 stack에서 뺀다
뺀 요소가 '('가 아닌 다른 요소라면 서로 쌍이 맞지 않으므로 false를 리턴한다.

풀이

const balancedBRackets = function (str) {
   let left = []
  let right = []

  if (str === "") {
    return true
  }

  for (let i = 0; i < str.length; i++) {
    if (str[i] === '(') {
      left.push(str[i])
    } else {
      right.push(str[i])
    }
  }
  let output = []
  //열린 만큼 닫혀야 하므로, '(' 이후의 값들은 모두 ')'여야 함을 이용한다.
  for (let j = left.length - 1; j < str.length; j++) {
    if (str[j] === ')') {
      output.push(str[j])
    }
  }
  if (left.length === output.length){
    return true
  }else{
    return false
  }
}
}
//stack을 이용한 풀이
const balancedBrackets = function (str) {
  const stack = [];
  const opener = '(';
  const closer = ')';

  for (let i = 0; i < str.length; i++) {
    if (str[i] === opener) {
      stack.push(str[i]);
    } else if (str[i] === closer) {
      const top = stack.pop();
      if (top !== opener) {
        return false;
      }
    }
  }

  return stack.length === 0;
};

깨달은 점

stack을 활용한 문제였는데, 처음에는 for문을 통해 풀었다. 하지만 반복문을 2번 돌리는 것보다, stack을 활용해 한번만 돌리는 것이 시간복잡도 측면에서 좋은 것 같다.
점점 stack에 대해서 익숙해져야 하는데 연습이 부족하다