Algorithm problem-17

1. 문제

• 괄호들로 이루어진 문자열을 받아 올바르게 닫혀있는지를 boolean으로 리턴

2. 시도

• 오프너와 클로저의 견본을 만든다
• 클로저가 나오면 그와 맞는 오프너가 나오는지 비교해줘야 한다
• 클로저를 키 값으로 갖고, 그와 맞는 오프너를 벨류로 갖는 견본 배열을 만든다
• 오프너는 열리는데로 새로운 배열에다 잘라서 저장해주고
• 클로저가 나오면, 앞에 나왔던 오프너가 그와 맞는 오프너인지를 비교해준다
• 잘 맞게 나오면 잘라주고 넘어가고, 안맞는 오프너가 나오면 리턴 폴스
• 마지막까지 돌리고 나왔을 때, 오프너에 남은게 있으면 리턴 폴스
• 다 돌면 리턴 트루

3. 수도코드

const balancedBrackets = function (str) {
  // 오프너와 클로저의 견본을 만든다
  let opener = '([{', closer = ')]}'
  // 오프너와 클로저 쌍으로 이루어진 객체를 만든다
  let partner = { ')':'(', '}':'{', ']':'[' };
  // 오프너가 나오면 저장해 줄 빈 배열을 생성
  let opened = []
  // str의 문자열을 뽑아서 작업을 해주자
  while (str.length > 0) {
    // 오프너면 오픈드에 저장해주고, 잘라내준다
    if (opener.includes(str[0])) {
      opened.push(str[0])
      str = str.slice(1)
    }
    // 클로저가 나오면, 클로저의 짝이 오픈드의 마지막 요소와 같으면 지나가고 아니면 폴스
    else if (closer.includes(str[0])) {
      if (partner[str[0]] === opened.pop()) {
        str = str.slice(1)
      } else {
        return false;
      }
    }
  }
  if (opened.length > 0) {return false;}
  return true;
};

4. 레퍼런스

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;
};