알고리즘 문제풀이 11

자료구조의 가장 기본인 queue와 stack을 활용한 알고리즘 문제이다.

첫번째 문제는 stack 자료구조에서 단골 손님이라 할 수 있는
괄호의 쌍이 맞는지를 점검하는 문제이다.

var balancedParens = function(input){
    //() , {}, [] : 인풋값중에서 괄호가 이렇게 쌍으로 이루어져 있는지를 탐색
    //input값을 우선 spilt 해준다.
    //그리고 괄호 부분만 발라내서 새로운 배열에 넣어준다.
    let bracket = ["(",")","{","}","[","]"];
    let inputArr = input.split('');
    let res = [];
    for(let i=0; i<inputArr.length; i++){
        if(bracket.includes(inputArr[i])){
            res.push(inputArr[i]);
        }
        if(((res[res.length-2]==="(") && (res[res.length-1]===")"))
        || ((res[res.length-2]==="{") && (res[res.length-1]==="}"))
        || ((res[res.length-2]==="[") && (res[res.length-1]==="]"))){
            res.pop();
            res.pop()
        }
    }
    if(res.length >0){
        return false;
    }
    return true;
};

어떻게 보면 괄호에 해당하는지를 확인하고 결과값에 넣을때마다
결과값 배열에 짝이있는지 없는지 점검하고, 있으면 빼주는 형태로 계산한 것이다. FIFO 즉 먼저 들어온것이 먼저 나가는 queue의 자료구조를 활용하였다고 보면 될 것 같다.

그러나 pop을 한 번만 쓰도록 해줄수있지 않을까?
그러니까 처음에 무조건 전부다 push를 하지 말고, 하나씩 번갈아서 점검하면서 pop하고 push를 해주지 말기

var balancedParens = function (input) {
  let stack = [];

  for (let i = 0; i < input.length; i++) {
    var curr = input[i];
    if (curr === '(' || curr === '{' || curr === '[') {
      stack.push(curr);
    } else if (curr === ')' || curr === '}' || curr === ']') {
      let top = stack[stack.length - 1];//즉 가장 마지막 요소를 top이란 변수에 선언
      if (top === undefined) {
        // 이 말인 즉슨 집어넣어주려는 요소가 닫히는 괄호인데 stack에 넣어놓은 괄호가 없을때 즉, 열린 괄호보다 닫힌괄호가 먼저 앞인 경우에 false를 반환 
        // 열린 괄호보다 닫힌 괄호가 더 많을 때, ex) should return false for )
        return false;
      }
      // 넣어놓은 배열에서 가장 마지막 요소가 열린 괄호이고, input에서 막 집어넣으려는 요소가 이에 대응하는 닫힌 괄호인 경우
      if (top === '(' && input[i] === ')') {
        stack.pop();
      } else if (top === '{' && input[i] === '}') {
        stack.pop();
      } else if (top === '[' && input[i] === ']') {
        stack.pop();
      }
    }
  }
  if (stack.length !== 0) {
    //닫힌 괄호보다 열린 괄호가 더 많을 때, ex) should return false for (
    return false;
  }
  return true;
};