JavaScript로 가장 긴 유효한 괄호 부분 문자열 찾는 방법

문자열 처리 알고리즘 문제 중 하나로, '(' 와 ')' 두 가지 문자로만 구성된 문자열이 주어졌을 때, 그중에서 가장 긴 유효한(잘 짜인) 괄호 부분 문자열의 길이를 찾는 방법을 알아보겠습니다.

유효한 괄호란?

괄호 집합이 '잘 짜인(well-formed)' 상태가 되려면, 모든 여는 괄호 '('에 대해 반드시 짝이 되는 닫는 괄호 ')'가 존재해야 합니다.

예를 들어 다음과 같습니다.

'(())()' → 잘 짜인 괄호 문자열입니다
'())'   → 잘 짜인 괄호 문자열이 아닙니다
'()()()' → 잘 짜인 괄호 문자열입니다

해결 접근 방식: 스택(Stack) 활용

이 문제는 스택 자료구조를 이용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 여는 괄호 '('를 만나면 해당 인덱스를 스택에 push합니다.
• 닫는 괄호 ')'를 만나면 스택의 최상단 요소와 짝을 이루는지 확인하고, 짝이 맞으면 pop합니다.
• 짝을 이루지 못하는 경우에는 해당 인덱스를 경계 표시로 push합니다.

모든 문자를 순회한 후, 스택에 남아 있는 인덱스들은 매칭되지 않은 괄호들의 위치를 나타냅니다. 이 인덱스들 사이의 간격 중 가장 큰 값이 곧 가장 긴 유효한 괄호 부분 문자열의 길이가 됩니다.

코드 예제

const str = '(())()(((';

const longestValidParentheses = (str = '') => {
  var ts = str.split('');
  var stack = [], max = 0;

  ts.forEach((el, ind) => {
    if (el == '(') {
      stack.push(ind);
    } else {
      if (stack.length === 0 || ts[stack[stack.length - 1]] == ')') {
        stack.push(ind);
      } else {
        stack.pop();
      }
    }
  });

  // 양 끝에 경계값 추가
  stack.push(ts.length);
  stack.splice(0, 0, -1);

  // 인접 인덱스 간 간격의 최댓값 계산
  for (let ind = 0; ind < stack.length - 1; ind++) {
    let v = stack[ind + 1] - stack[ind] - 1;
    max = Math.max(max, v);
  }

  return max;
};

console.log(longestValidParentheses(str));

동작 원리 설명

입력 문자열 '(())()(('을 기준으로 살펴보겠습니다.

1. 앞의 6개 문자 '(())()'는 서로 완벽하게 짝을 이루므로 스택에서 제거됩니다.
2. 마지막 3개의 여는 괄호 '((('는 짝이 없으므로 스택에 인덱스로 남습니다.
3. 순회 종료 후 스택의 양 끝에 -1과 문자열 길이 9를 추가하여 경계를 만듭니다.
4. 인접한 인덱스 사이의 간격을 계산하면, 매칭되지 않은 괄호들 사이의 유효한 구간 길이를 구할 수 있습니다.

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다.

6

즉, 문자열 '(())()(('에서 가장 긴 유효한 괄호 부분 문자열은 '(())()'이며, 그 길이는 6입니다.

시간 복잡도

이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n), 스택에 최대 n개의 인덱스가 저장될 수 있으므로 공간 복잡도 역시 O(n)입니다.