JavaScript에서 괄호 문자열 유효성 검사하기: 스택으로 해결하는 방법

문제 소개

여섯 가지 괄호 문자 '(', ')', '{', '}', '[', ']'만으로 구성된 문자열을 입력받아, 해당 문자열이 유효(valid)한지 판별하는 JavaScript 함수를 작성해 보겠습니다.

유효한 문자열의 조건

• 열린 괄호는 반드시 같은 종류의 닫힌 괄호로 닫혀야 합니다.
• 열린 괄호는 올바른 순서대로 닫혀야 합니다.

예시

• "()" → 유효한 괄호
• "()[]{}" → 유효한 괄호
• "(]" → 유효하지 않은 괄호 (괄호 종류가 일치하지 않음)

접근 방법: 스택(Stack) 활용

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

1. Map 객체에 각 여는 괄호와 대응되는 닫힌 괄호의 짝을 미리 저장합니다.
2. 문자열을 한 글자씩 순회하면서 여는 괄호를 만나면 스택에 push합니다.
3. 닫는 괄호를 만나면 스택에서 pop한 뒤, 해당 여는 괄호와 짝이 맞는지 확인합니다.
4. 모든 문자를 처리한 후 스택이 비어 있으면 유효한 문자열입니다.

구현 코드

const isValid = (str = '') => {
   const map = new Map();
   map.set('{', '}');
   map.set('(', ')');
   map.set('[', ']');
   const stack = [];
   for (let i = 0; i < str.length; i++) {
      if (map.has(str.charAt(i))) {
         // 여는 괄호라면 스택에 push
         stack.push(str.charAt(i));
      } else {
         // 닫는 괄호라면 스택에서 pop 후 짝 검사
         const open = stack.pop();
         if (map.get(open) !== str.charAt(i)) {
            return false;
         }
      }
   }
   // 모든 괄호가 짝을 이루었다면 스택은 비어 있어야 함
   return stack.length === 0;
};
console.log(isValid("()[]{}"));
console.log(isValid("(]"));

출력 결과

true
false

코드 동작 원리

"()[]{}"의 경우 모든 괄호가 올바른 순서로 짝을 이루므로 최종적으로 스택이 비어 true가 반환됩니다. 반면 "(]"는 여는 괄호 (에 대해 닫는 괄호 ]가 등장해 짝이 맞지 않으므로 즉시 false를 반환합니다.

또한 "([)]"처럼 교차된 순서로 닫히는 경우에도 짝 검사 단계에서 실패하고, "((("처럼 열린 괄호가 끝까지 남아 있는 경우에는 마지막 스택 길이 검사에서 걸러집니다.

시간 및 공간 복잡도

• 시간 복잡도: O(n) — 문자열을 한 번만 순회합니다.
• 공간 복잡도: O(n) — 최악의 경우 모든 여는 괄호가 스택에 저장될 수 있습니다.