자료구조(스택) - 1. 올바른 괄호

문제

괄호가 올바른 괄호면 'true', 그르면 'false'를 출력한다.
올바른 괄호는 여는 괄호와 닫는 괄호의 짝이 맞아야 한다.

// '('가 더 많은 경우
let b = "()()(";
console.log(solution(b)); //NO

// ')'가 더 많은 경우
let c = "()()())";
console.log(solution(c)); //NO

// '( )' 짝이 맞는 경우
let d = "()()";
console.log(solution(d)); //YES

 

 

풀이

JS에서 stack을 구현하려면 배열을 하나 만들어 주면 된다.

괄호로 이루어진 문자열을 반복 순회하면서 문자가 ' ( ' 인 경우에는 배열에 push를 해준다.

문자가 ' ) ' 인 경우에 pop을 해서 undefined 인 경우, 즉 pop한 요소가 없다면 짝이 맞지 않으므로 NO를 return 한다.

위의 조건이 아닌 경우에는 그냥 pop을 해준다.

 

반복 순회를 다 마치고 나서는 stack 배열의 길이를 확인한다.

만약에 길이가 0이면 push와 pop이 짝을 이뤄서 실행되었다는 뜻이고

길이가 0보다 크다면 push가 더 된 상황이기 때문에 NO를 return 해준다.

위의 조건이 아닌 경우에는 YES를 return 해준다.

 

 

코드

function solution(s){
  let answer="YES";
  let stack = [];

  for (let x of s) {
    if (x === '(') stack.push(x);
    else if (x === ')') {
      if (stack.pop('(') === undefined) return "NO"; // '(' 가 많은 경우
      stack.pop();
    }
  }
  if (stack.length !== 0) answer = "NO";
  return answer;
}
// '('가 더 많은 경우
let a="(()(()))(()";
console.log(solution(a)); //NO
let b = "()()(";
console.log(solution(b)); //NO

// ')'가 더 많은 경우
let c = "()()())";
console.log(solution(c)); //NO

// '( )' 짝이 맞는 경우
let d = "()()";
console.log(solution(d)); //YES

 

 

출처

자바스크립트 알고리즘 문제풀이(코딩테스트 대비) - 인프런 | 강의