Valid Parentheses

November 27th 2018

문제

Write a function called that takes a string of parentheses, and determines if the order of the parentheses is valid. The function should return true if the string is valid, and false if it's invalid.

Examples

"( )" => true

") ( ( ) ) )" => false

"(" => false

"( ( ) ) ( ( ( ) ( ) ) ( ) )" => true

Argument로 받는 괄호의 짝이 맞는지 아닌지 Boolean으로 반환하는 함수를 만드는 문제입니다. 기존에 이 문제를 여는 괄호를 만나면 +1을 하고 닫는 괄호를 만나면 -1을해서 총 합이 0이면 true, 그렇지 않으면 false를 반환하도록 아래와 같이 작성을 했습니다.

function validParentheses(parens) {
  let sum = 0;

  for (let i = 0; i < parens.length; i++) {
    parens[i] === '(' ? sum++ : sum--;

    if (sum < 0) {
      return false;
    }
  }

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

하지만 최근에 자료구조를 학습해서, 자료구조를 이용해 문제를 해결하는 방법을 고민하고 있습니다. 위 문제는 stack을 이용해 아래와 같이 해결할 수 있습니다.

여는 괄호가 나오면 Stack에 여는 괄호를 쌓고, 닫는 괄호를 만나면 stack을 하나씩 pop해줍니다. 최종적으로 stack의 길이가 0이면 true를 그렇지 않으면 false를 반환합니다.

function validParentheses(parens) {
  const stack = [];
  const rest = [];
  const arr = parens.split('');

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === '(') {
      stack.push('(');
    } else {
      if (stack.length === 0) {
        rest.push(')');
      } else {
        stack.pop();
      }
    }
  }

  return stack.length === 0 && rest.length === 0 ? true : false;
}

불필요한 로직 제거 후 아래와 같이 다시 풀어 보았어요.

function validParentheses(parens) {
  const stack = [];

  for (let i = 0; i < parens.length; i++) {
    const parenthesis = parens[i];
    
    if (parenthesis === "(") {
      stack.push(parenthesis);
      continue;
    }
    
    const prev = stack.pop();
    
    if (prev !== "(") {
      return false;
    }
  }
  
  return !stack.length
}

Handmade with .