[프로그래머스] 올바른 괄호 - JS

올바른 괄호

❓ 문제설명

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다.

 

예를 들어

"()()" 또는 "(())()" 는 올바른 괄호입니다.

")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

 

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는  solution 함수를 완성해 주세요.

🚫 제한조건

문자열 s의 길이 : 100,000 이하의 자연수

문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

✔ 입출력 예

s	answer
"()()"	true
"(())()"	true
")()("	false
"(()("	false

💡 풀이

function solution(s){
  // 내 풀이
  // 큐를 사용해서 문자열을 순차적으로 순회하고
  // 스택을 사용하여 문자를 저장하며 괄호의 완성을 체크한다.
  const stack = []
  let queue = s

  // '(', ')' 문자의 수가 다르다면 false
  if (s.replace(/\)/g,'').length !== s.replace(/\(/g,'').length) {
    return false
  }

  while (queue.length > 0) {
    const c = queue.charAt(0)
    queue = queue.substring(1)

    if (stack.length === 0 && c === ')') {
      // 스택이 ')'로 시작하면 false
      return false
    }

    if (c === ')' && stack[stack.length - 1] === '(') {
      // 괄호가 완성되면 스택에서 괄호 쌍을 비운다.
      stack.pop()
    } else {
      stack.push(c)
    }
  }

  return stack.length > 0 ? false : true

  // 다른사람 풀이
  // 괄호를 각 1, -1로 매칭해서 문자열을 돌면서 그 합을 확인한다. (0이라면 true)
  let cum = 0

  // '(', ')' 문자의 수가 다르다면 false
  if (s.replace(/\)/g,'').length !== s.replace(/\(/g,'').length) {
    return false
  }

  for (let paren of s) {
    cum += paren === '('? 1: -1
    if(cum < 0) {
      // ')'로 시작한다면 false
      return false
    }
  }
  return cum === 0? true: false;
}

📝 해설

스택과 큐를 사용해서 문자열 s를 큐 대기열로 순회하여 스택에 쌓고, 스택에서는 괄호가 완성 되었을 경우 괄호 쌍을 삭제하여 최종적인 스택의 길이가 0이라면 true / 그 외에는 false를 리턴하였다. 이 때 시간초과가 발생하기 때문에 최초에 '(' 과 ')' 갯수가 동일하게 들어오는지 그리고 스택이 비어있을 때 처음 들어오는 값 이 ')' 인지 확인해서 미리 false를 리턴하는 로직을 넣어서 시간초과를 해결하였다.

 

다른사람의 풀이를 보다보니 괄호를 각각 1 과 -1에 매칭하여 단순히 더하는 것으로 해결한 방법이 있었다. 속도나 메모리는 차이가 없었지만 생각을 전환해볼 수 있는 방법이라 따로 추가하였다.

📚 참고자료

- https://kimby.tistory.com/84 (String 메소드)