Algorithm 10장 - 괄호쌍 구하기

Algorithm

유효한 괄호쌍

문제

• 입력된 괄호 값들이 모두 쌍이 맞게 올바른지를 판단해 모두 쌍이 맞으면 true 그렇지 않으면 false를 출력하세요.

• 입력된 괄호 값들이 유효한 경우들은 다음에 해당합니다.

1. 열린 괄호는 같은 타입의 닫힌 괄호로 닫혀있어야 한다.
2. 열린 괄호는 올바른 순서대로 닫혀야만 한다.
3. 모든 닫힌 괄호는 그에 상응하는 같은 타입의 열린 괄호를 갖고 있다.

• 입력값을 통해 들어오는 괄호는 (),[],{}로만 이루어져 있습니다.

입력

• 인자 1 : str
  • string 타입으로 된 문장

출력

• boolean 타입을 리턴해야 합니다.

주의 사항

• 입력값을 통해 들어오는 괄호는 (),[],{}로만 이루어져 있습니다.
• 입력값으로 들어오는 str의 길이는 0부터 10^4승 까지 입니다.

입출력 예시

const result1 = isValid("[]");
console.log(result1); // true

const result2 = isValid("[)");
console.log(result2); // false

const result3 = isValid("[]{}()");
console.log(result3); // true

const result4 = isValid("[]{)()");
console.log(result4); // false

힌트

• 스택을 사용해 보세요.
• 열린 괄호인 경우 스택에 push합니다.
• 닫힌 괄호인 경우에는 스택의 top을 확인하고, 해당 닫힌 괄호와 짝이 맞는 열린 괄호인지를 확인합니다.

코드

const isValid = (str) => {};

코드 설명

const isValid = (str) => {
  if (str.length === 0) return false;
  let stack = [];
  // str을 비교해서 stack에 넣는다.

  // 쌍을 정해 줄 예시를 작성한다.
  let sign = {
    "(": ")",
    "[": "]",
    "{": "}",
  };

  // str을 나눈다.
  let word = str.split("");

  for (let i = 0; i < word.length; i++) {
    if (word[i] === "(" || word[i] === "[" || word[i] === "{") {
      stack.push(word[i]);
    } // 열린 괄호인 경우 stack에 넣는다.
    else {
      // 닫힌 괄호인 경우는 스택의 마지막 값을 확인해서, 짝이 맞는 열린 괄호인지를 확인한다.
      let save = stack.pop();
      if (word[i] !== sign[save]) return false;
      // word[i]는 닫힌 괄호, sign[stack에 들어가 있는 마지막 열린괄호]
    }
  }
  if (stack.length !== 0) return false; // pop해서 사라져야 하는데 값이 남아있다는 건 짝이 안 맞는다.
  return true;
};

코드 설명

• if(str.length === 0) return false
  • 아무런 괄호쌍을 입력하지 않으면 false를 출력한다.
• let stack = []
  • stack 역할을 할 빈 배열을 작성한다.
• let sign = {...}
  • 입력한 열린 괄호에 따라 닫힌 괄호를 작성할 짝을 만들어 놓는다.
• let word = str.split('')
  • 입력받은 괄호쌍을 하나씩 나눈다.
• for(...){...}
  • if(word[i] === "("||word[i] === "["||word[i] === "{")
    • 입력받은 인자가 열린 괄호일 시,
  • stack.push(word[i])
    • stack에 열린 괄호를 넣어놓는다.
  • let save = stack.pop
    • 만약 닫힌 괄호일 경우 else문으로 오게 되고, 현재 stack에 들어있는 열린 괄호와 짝을 비교하기 위해 stack에 마지막으로 입력되어 있는 열린 괄호를 저장해놓는다.
  • if(word[i] !== sign[save]) return false
    • 미리 작성해 놓았던 괄호 짝을 가진 객체인 sign에 방금 저장한 열린 괄호를 비교하여, 열린 괄호의 짝과 닫힌 괄호가 일치하지 않는다면 잘못된 짝이라는 말이기 때문에 false를 출력한다.
  • if(stack.length !== 0) return false
    • 모든 순서를 거쳐 짝을 확인했는데도 stack에 값이 남아있다는 것은 열린 괄호가 짝 없이 하나만 입력됐다는 뜻이기 때문에 false를 출력한다.
  • return true
    • 모든 조건문을 다 거쳤을 경우 true를 리턴한다.