2021.8.10 TIL 괄호 여닫힘 문제 _ 스택 알고리즘

올바른 괄호

괄호가 잘 닫혀 있는지 체크하는 함수

 

function solution(str) {
  let answer;
  // code here
  return answer;
}

let ex1 = '(()(()))(()'
console.log(solution(ex1)); // false
let ex2 = '(()()))'
console.log(solution(ex2)); // false
let ex3 = '(())()'
console.log(solution(ex3)); // true

 

 

답)

 

function solution(str) {
  let open = '(', close = ')';
  let sum = 0;

  for(let el of str) {
    if(sum < 0) return false;
    el === open ? sum++ : sum--
  }

  return sum === 0 ? true : false;
};

 

 

답2) stack 자료구조

• '('이면 배열(에 담기
• ')' 이면 배열에서 맨 나중에 넣은 '('를 삭제

 

function solution(str) {
  let answer = true;
  let open = '(', close = ')';
  let stack = [];

  for(let el of str) {
    if(el === open) {
      stack.push(el)
    } else {
      if(stack.length === 0) return false;
      stack.pop();
    }
  }

  return answer;
}

 

 

괄호 문자 제거

괄호안에 문자를 제거하고, 괄호밖 문자만 출력하는 함수

 

function solution(str) {
  let answer;
  // code here
  return answer;
}

let ex = '(A(BC)D)EF(G(H)(IJ)K)LM(N)'
console.log(solution(ex)); // EFLM

 

 

답)

 

function solution(str) {
  let answer = '';
  const open = '(', close = ')';
  let sum = 0;

  for(const el of str) {
    if(sum === 0 && el !== open) {
      answer += el;
    }
    if(el === open) {
      sum++;
    }
    if(el === close) {
      sum--;
    }
  }

  return answer;
}

 

 

답2) stack 을 이용한다

 

function solution(str) {
  const open = '(', close = ')';
  const stack = [];

  for(const el of str) {
    if(el === close) {
      while(stack.pop() !== open)
    }
    else {
      stack.push(el)
    }
  }

  return stack.join('');
}