Stack 기반 LIFO 구조를 통한 O(N) 시간 복잡도의 괄호 검증 설계

LeetCode Solution: 20. Valid Parentheses

Vansh Aggarwal2026년 5월 16일7분beginner

AI 요약

Context

문자열 내 괄호의 짝 맞춤 및 순서 검증을 위한 효율적 처리 방식 요구. 단순 순차 탐색으로는 중첩된 괄호의 계층 구조를 추적하는 데 한계가 있음.

LIFO(Last-In First-Out) 특성을 가진 Stack을 도입하여 가장 최근에 열린 괄호를 최우선으로 매칭하는 구조 설계
Hash Map을 활용하여 닫는 괄호를 Key로, 대응되는 여는 괄호를 Value로 정의함으로써 매칭 조건 확인의 시간 복잡도를 O(1)로 최적화
여는 괄호 발견 시 Stack에 Push하여 대기 상태로 유지하고, 닫는 괄호 발견 시 Pop을 통해 즉시 대응 여부를 검증하는 로직 구현
Stack이 비어있음에도 닫는 괄호가 나타나는 경우나, 최종 처리 후 Stack에 잔여 데이터가 남는 경우를 예외 처리하여 무결성 확보
단일 루프 기반의 선형 탐색을 통해 불필요한 중복 연산을 제거한 최적의 경로 설계

실천 포인트

1. 중첩 구조 분석 시 LIFO 기반의 Stack 적용 검토

2. 반복적인 조건문 대신 Hash Map을 통한 매핑 관계 정의로 코드 가독성 및 유지보수성 향상

3. 빈 스택 상태에서의 Pop 시도 등 Edge Case에 대한 방어 코드 작성 확인

태그