Algorithm - 올바른 괄호인지 판단하기

문제 설명

s는 여러 괄호들로 이루어진 String 인자입니다. s가 유효한 표현인지 아닌지 true/false로 반환해주세요.
종류는 '(', ')', '[', ']', '{', '}' 으로 총 6개 있습니다. 아래의 경우 유효합니다.

• 한 번 괄호를 시작했으면, 같은 괄호로 끝내야 한다.
• 괄호 순서가 맞아야 한다.

입출력 예

• s = "()"
  return true
  
• s = "()[]{}"
  return true
  
• s = "(]"
  return false
  
• s = "([)]"
  return false
  
• s = "{[]}"
  return true

나의 풀이

function isValid(s) {
  let answer = false;
  let stack = [];
  let arrS = s.split('');

  function isOpened(input) {
    let value = false;

    if (input === '(' || input === '{' || input === '[') {
      value = true;
    }

    return value;
  }

  function isMatched(input1, input2) {
    let value = false;

    if (input1 === '(' && input2 === ')'){
        value = true;
    } else if (input1 === '{' && input2 === '}') {
        value = true;
    } else if (input1 === '[' && input2 === ']') {
        value = true;
    }

    return value;
  }

  stack.push(arrS[0]); //첫번째꺼는 일단 푸시.

  for (let i = 1; i < arrS.length; i++) {
    if (isOpened(arrS[i])) {  //열림기호
      stack.push(arrS[i]);
    } else {  //닫힘기호
      let poped = stack.pop();

      if (isMatched(poped, arrS[i])) { //짝 맞음

      } else {  //짝 안맞음
        return false;
      }
    }
  }

  if(stack.length === 0){
    answer = true;
  }
  return answer;
}

console.log(isValid(''))

풀이 설명

• 먼저 문제를 풀기 전에 준비물이 필요했다.
• return되는 값은 boolean값이기 때문에 true 혹은 false로 지정해준다.
• 스택이 쌓일 빈 배열을 준비하고 주어진 s라는 문자열을 쪼개 배열로 만들어줄 arrS를 준비한다.
• 온전한 괄호가 만들어 지려면 무조건 열린 괄호가 먼저 나와야한다. 그러므로 열린 괄호 인지를 알 수 있는 isOpened 함수를 준비한다.
• 또한 괄호가 만들어지려면 열린 괄호가 나온 뒤 그에 맞는 닫힌 괄호가 나와줘야 하기 때문에 열린 괄호에게 맞는 짝인지 판단해줄 수 있는 isMatched 함수를 준비한다.

 let answer = false;
  let stack = [];
  let arrS = s.split('');


  function isOpened(input) {
    let value = false;

    if (input === '(' || input === '{' || input === '[') {
      value = true;
    }

    return value;
  }


  function isMatched(input1, input2) {
    let value = false;

    if (input1 === '(' && input2 === ')'){
        value = true;
    } else if (input1 === '{' && input2 === '}') {
        value = true;
    } else if (input1 === '[' && input2 === ']') {
        value = true;
    }

    return value;
  }

다음으로 오는 내용을 말로 풀어 설명하자면 이렇다.

스택(빈 배열)에 주어진 원소들을 하나씩 넣는다.
1. 넣을 원소가 열린 괄호라면 무조건 넣는다.(push)
2. 넣을 원소가 닫힌 괄호라면 기존 원소에서 하나를 빼(pop) 짝이 맞는지 확인한다.
	2-1. 짝이 맞다면 뺀 상태 그대로 넘어간다.
	2-2. 짝이 맞지 않다면 false를 반환한다.
3. 반복문이 끝났을 때 스택에 아무것도 남아있지 않다면 true를 반환한다.

stack.push(arrS[0]); //첫번째꺼는 일단 푸시.

  for (let i = 1; i < arrS.length; i++) {
    if (isOpened(arrS[i])) {  //열림기호
      stack.push(arrS[i]);
    } else {  //닫힘기호
      let poped = stack.pop();

      if (isMatched(poped, arrS[i])) { //짝 맞음

      } else {  //짝 안맞음
        return false;
      }
    }
  }

  if(stack.length === 0){ //스택이 비었는지 확인
    answer = true;
  }
  return answer;
}

느낀 점

stack이라는 새로운 구조에 대해 알고 기억하기 위해 기록한다.
문제를 풀면서 자료구조 공부라는 또 하나의 과제가 생겼다.
이해를 하고 나니 간단한 원리이지만 이걸 또 어떻게 응용해서 사용하는가는 조금 더 경험치가 쌓여야 가능할 듯 하다.

참고-https://us05web.zoom.us/j/89777322996?pwd=MDVKVThEQStpYzUwN0RyS0VDbmtTdz09