[알고리즘]balancedBrackets

문자열을 입력받아 문자열 내의 모든 괄호의 짝이 맞는지 여부를 리턴.(boolean)

혼자서 풀어보다 잘 안 돼서 알고리즘 참고했음.
나는 닫힌 괄호의 개수를 할당한 변수를 만드려고 했는데, 래퍼런스에서는 stack이라는 변수에 배열로 괄호의 상태를 확인한다.

opener라는 건 열리는 괄호인 '('를 뜻하고,
closer는 닫히는 괄호인 ')'를 뜻하는 변수이다.

반복문을 돌리면서 만약 opner에 해당하면 stack에 쌓이도록 하고,
closer에 해당하면 opner들을 넣어둔 stack에서 opner를 하나 제거한다.

이렇게 지워나가기를 반복하다가 stack에서 지워지는 요소를 담은 top이 opner에 해당하지 않는다면 (undefined) 짝이 맞지 않는다는 뜻이므로 false를 리턴하면 된다.

맨 마지막 리턴문에서는 stack의 length가 0인지 불리언 타입을 리턴하도록 했는데, 짝이 다 맞아서 stack이 빈 배열이 되거나, 혹은 애초에 들어온 str가 빈 문자열이어서 stack이 빈 배열이면 true를 리턴할 수 있다.

//괄호의 종류가 '(',')'하나 뿐일 때 
// naive solution
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;
};

advanced 단계의 테스트를 통과하려면 "("외에도 "{","[" 까지 총 세 종류의 괄호들을 분류해서 닫혔는지 확인 해주어야 했다.

처음과 같이 stack을 만드는 건 동일하지만 opner 변수에는 각 opener 괄호들이 키가 되고, closer 괄호가 값이 되는 객체가 할당된다.

반복문 내에서 만약 str[i]가 opnener에 해당하면 stack 배열 속으로 push 된다.
opnener에 해당하지 않지만 closer 문자열 속에 해당(includes가 true)하는 경우에는 top과 pair를 비교한다.
pair는 opnener에 top을 넣었을 때 나오는 closer 괄호 값인데, 그 값이 str[i]와 동일하지 않으면 false를 반환한다.

'[(]{)}'이나 '[]}{()'같은 경우는 false에 해당한다.
(순서도 맞아야하고, 짝도 맞아야 하는듯)

//advanced 
const balancedBrackets = function (str) {
  const stack = [];
  const opener = {
    '{': '}',
    '[': ']',
    '(': ')',
  };
  const closer = '}])';

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

  return stack.length === 0;
};