[Leetcode] 32. Longest Valid Parentheses

Problem

문제 링크

올바른 괄호가 연속적으로 나오는 최대 길이.

Solution

올바른 괄호를 처리하기 위해서 왼쪽에서 오른쪽으로 반복문을통해 열린괄호(left)와 닫힌괄호(right)의 쌍이 일치하는지 확인한다.

먼저 열린괄호에대한 최대개수를 구하고 그 후에 닫힌괄호에대한 최대개수를 구함으로써 모든 괄호를 검사한다.
열린괄호의 검사를 시작할땐, 열린 괄호로 시작해야 올바른 괄호임으로 right가 left를 넘지 않도록(넘었다면 카운팅 x)한다.
열린 괄호로 시작할때 닫힌괄호와 같은 갯수를 가지는 순간 올바른 문법의 끝이기 때문에 이때 괄호의 갯수를 비교하여 최대값을 저장한다.

같은 방법으로 오른쪽에서 왼쪽으로 반복문을 진행하면서 닫힌괄호에대한 열린괄호가 올바르게 있는지를 확인하여 최대 개수를 구한다.

JS Code

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function (s) {
  let left = 0,
    right = 0
  let answer = 0

  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') left++
    else if (s[i] === ')') right++

    if (left === right) answer = Math.max(answer, right * 2)
    else if (left < right) left = right = 0
  }

  left = right = 0

  for (let i = s.length - 1; 0 <= i; i--) {
    if (s[i] === '(') left++
    else if (s[i] === ')') right++

    if (left === right) answer = Math.max(answer, left * 2)
    else if (left > right) left = right = 0
  }

  return answer
}