20. Valid Parentheses

난이도: 쉬움 (Easy)

링크: LeetCode 20 — Valid Parentheses

풀이 날짜: 2025/10/22

 

1. 문제 이해

입력:

s = "()[]{}"

출력:

true

괄호로 구성된 문자열이 주어질 때, 올바르게 짝이 맞는지 판단하는 문제다. 모든 열린 괄호는 같은 종류의 닫힌 괄호로 닫혀야 하며, 올바른 순서로 닫혀야 한다.

입력	결과	이유
"()"	true	괄호 짝이 맞음
"()[]{}"	true	여러 종류의 괄호가 올바르게 닫힘
"(]"	false	서로 다른 괄호가 짝지어짐
"([)]"	false	괄호 순서가 잘못됨
"{[]}"	true	중첩 구조로도 올바르게 닫힘

 

2. 접근 방식 — Stack (스택)

이 문제는 스택 자료구조의 대표적인 응용 문제다.

 

핵심 아이디어:

• 열린 괄호는 스택에 push한다.
• 닫힌 괄호가 등장하면, 스택의 top을 pop해서 짝이 맞는지 확인한다. -> 짝이 맞지 않으면 바로 false 리턴한다.
• 전부 확인했을 때 스택이 비어 있으면 유효한 문자열이다. -> 잘못된 예시로, 열린 괄호만 입력으로 주어진 경우 for 구문은 통과하지만 스택이 비어있지 않은 상태(닫히지 않은 상태)이므로 false 이다.

 

 

3. 풀이 코드

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
  if (s.length % 2 === 1) return false; // 홀수 길이는 무조건 false
  const stack = [];
  const pMap = {
    '(': ')',
    '{': '}',
    '[': ']'
  };

  for (let char of s) {
    if (pMap[char]) {
      stack.push(char); // 여는 괄호 → push
    } else {
      const popped = stack.pop(); // 닫는 괄호 → 이전 괄호 pop
      if (pMap[popped] !== char) return false; // 짝이 맞지 않으면 false
    }
  }

  return stack.length === 0; // 모든 괄호가 닫혀야 함
};

구분	복잡도	설명
시간 복잡도	O(N)	문자열을 한 번 순회
공간 복잡도	O(N)	스택에 최대 N개의 괄호가 쌓일 수 있음

 

4. 핵심 정리

개념	설명
문제 유형	Stack, String Parsing
핵심 아이디어	열린 괄호 → push, 닫힌 괄호 → pop 후 매칭 확인
시간 복잡도	O(N)
공간 복잡도	O(N)
포인트	괄호 문제의 기본 구조는 항상 스택으로 접근한다.

이 문제는 스택의 기본 원리를 정확히 이해하고 있다면 매우 깔끔하게 해결된다. 괄호 짝 문제뿐만 아니라, 나중에 배우게 될 수식 평가, HTML 태그 검증, 파서 구현 등에서도 동일한 패턴이 등장한다.