32. Longest Valid Parentheses

문제링크: https://leetcode.com/problems/longest-valid-parentheses/

가장 긴 괄호가 완성되는 길이를 구하는 문제다.

Solution

1. Iteration with count array

완전탐색에 가까운 방식인데 추가배열을 이용해 조금 더 개선시킨 방법이다. 새 배열을 만들어 ( 의 경우 +1, )의 경우 -1을 연산해 넣고, 이후 이 정보를 바탕으로 길이를 구한다.

Algorithm

• 먼저 count배열을 만든다. 이 배열은 앞에서부터 (의 개수는 +1, )의 개수는 -1을해 "(()"의 경우 [1,2,1]이 된다.
• count배열을 이용해 완전탐색을 한다. 시작지점(left)을 기준으로 길이를 늘려가면서 탐색한다.
• count[left - 1] 의 값보다 작은 값을 만나면 초과해서 닫힌 괄호가 나타난 것으로 left + 1을 하고 다시 탐색한다.
• count[left - 1]과 동일한 값을 만나면 모든 괄호가 닫힌 것으로 그 길이를 계산해 result와 비교해 갱신한다.

var longestValidParentheses = function(s) {
  const count = new Array(s.length);
  let c = 0;
  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') {
      count[i] = ++c;
    } else {
      count[i] = --c;
    }
  }
  // Iteration with count arr
  let result = 0;
  let left = 0;
  while (left + result < s.length) {
    const curCount = left > 0 ? count[left - 1] : 0;
    for (let i = left; i < s.length; i++) {
      if (count[i] < curCount) {
        break;
      } else if (count[i] === curCount) {
        result = Math.max(result, i - left + 1);
      }
    }  
    left++;
  }
  return result;
};

총 O(n^2)의 시간복잡도와 O(n)의 공간복잡도가 필요하다. 단순한 완전탐색(배열을 지정하고 괄호여부를 확인)하는 방법은 O(n^3)의 시간복잡도를 가지는 것과 비교해 다소 효율적이지만 괄호의 특성을 최대한 활용하지 못한 점에서 아쉬운 방법이다.

2. Stack

괄호의 특성을 잘 나타내는 것은 아무래도 스택이다. stack을 이용해 괄호가 시작된 지점을 저장하고 )을 만나면 stack의 값을 지우면서 이전에 있던 괄호의 위치로 현재 완성된 괄호의 길이를 얻는 방식이다.

Algorithm

• stack에 저장되는 것은 남아있는 괄호의 위치로 처음에는 없으므로 0의 앞좌표인 [-1]을 저장해준다.
• (를 만나면 stack에 현재 좌표를 저장한다.
• )를 만나면 stack의 가장 위의 값을 pop하고 stack에 남아있는 가장 최근값(peek or at(-1))을 통해 완성된 괄호의 길이i - stack.at(-1)를 얻는다.
• 만약 )으로 pop을 한 후 stack에 남은 값이 없다면 초과해서 닫은 것으로 현재 좌표를 저장해준다.
• 얻은 완성된 괄호 길이와 maxLength를 비교해 갱신한다.

var longestValidParentheses = function(s) {
  // Stack
  const stack = [-1];
  let maxLength = 0;
  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') {
      stack.push(i);
    } else {
      stack.pop();
      if (stack.length === 0) {
        stack.push(i);
      } else {
        maxLength = Math.max(maxLength, i - stack.at(-1));
      }
    }
  }
  return maxLength;
};

한번의 탐색O(n)의 시간복잡도를 통해 완성된 괄호의 값을 구할 수 있다. stack이 괄호의 특성을 최대한 사용하는 것은 알고있었지만 좌표를 기록해 완성된 괄호의 길이를 구하는 방식은 새로웠다.