LeetCode

LeetCode 20 Valid Parentheses 풀이: 괄호 짝과 순서를 확인하는 스택

2026년 10월 4일

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

문제: 20. Valid Parentheses
출처: LeetCode
학습: 스택 자료구조 학습 가이드
자체 판단 난이도: Level 2

괄호의 종류뿐 아니라 가장 최근에 열린 괄호부터 닫아야 하는 순서도 확인해야 한다. 스택의 LIFO 성질을 적용하면 한 번의 문자열 순회로 판정할 수 있어 Level 2로 판단했다.

문제 원문과 제한 조건은 변경될 수 있으므로 제출 전에 공식 문제 페이지를 다시 확인하세요.

1. 문제 요약

괄호 문자 (, ), {, }, [, ]로 이루어진 문자열 s가 주어질 때 괄호가 올바르게 열리고 닫혔는지 판정한다.

문자열이 올바르려면 다음 조건을 모두 만족해야 한다.

여는 괄호는 같은 종류의 닫는 괄호와 짝을 이룬다.
괄호는 올바른 중첩 순서로 닫힌다.
닫는 괄호마다 앞서 열린 대응 괄호가 있어야 한다.
문자열이 끝났을 때 닫히지 않은 여는 괄호가 없어야 한다.

예를 들어 "([])"는 올바르지만, "([)]"는 괄호 종류는 모두 있지만 중첩 순서가 틀려 올바르지 않다.

문자열 길이는 1 이상 10^4 이하이며, 입력은 위 여섯 가지 괄호 문자로만 구성된다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

괄호 상태와 스택

여는 괄호를 만날 때마다 스택에 저장한다. 닫는 괄호를 만나면 스택 top이 해당 괄호와 짝을 이루는지 확인한다.

여는 괄호: (, [, {  -> push
닫는 괄호: ), ], }  -> top과 짝을 확인한 뒤 pop

스택은 마지막에 들어온 원소가 먼저 나오는 LIFO 구조다. 괄호가 중첩되면 가장 최근에 열린 괄호가 먼저 닫혀야 하므로 스택의 처리 순서와 일치한다.

스택 top이 다음 닫는 괄호의 짝을 정하는 이유

괄호가 닫힐 때는 지금까지 열린 괄호 중 가장 최근에 열린 것이 닫혀야 한다. 여는 괄호의 전체 개수만 세어서는 종류와 순서를 판정할 수 없다.

예를 들어 "([)]"에서는 ( 다음에 [가 열렸으므로 다음 닫는 괄호는 ]여야 한다. 그 전에 )가 나오면 스택 top [와 짝이 맞지 않아 잘못된 문자열로 판정한다.

상태 전이와 경계 처리

각 문자를 왼쪽부터 순회하며 다음 규칙을 적용한다.

여는 괄호이면 스택에 넣는다.
닫는 괄호인데 스택이 비어 있으면 대응하는 여는 괄호가 없으므로 False를 반환한다.
스택 top이 현재 닫는 괄호의 짝이 아니면 순서가 잘못된 것이므로 False를 반환한다.
짝이 맞으면 top을 제거한다.
문자열을 모두 확인한 뒤 스택이 비어 있어야 True다.

문자열 길이가 홀수이면 괄호가 짝을 이룰 수 없으므로 먼저 False를 반환해도 된다. 다만 이 조기 검사가 없어도 스택 순회와 마지막 잔여 상태 확인으로 판정할 수 있다.

오답 접근과 반례

여는 괄호와 닫는 괄호의 전체 개수만 세면 순서 오류를 놓친다.

s = "([)]"

여는 괄호 2개와 닫는 괄호 2개로 개수는 같지만 [가 열린 상태에서 )가 먼저 나왔으므로 올바르지 않다. 스택 top과 닫는 괄호의 종류를 매번 비교해야 한다.

"())"처럼 닫는 괄호가 먼저 나오는 경우에는 스택이 비어 있을 수 있다. 빈 스택에서 top을 읽으면 오류가 발생하므로 닫는 괄호를 처리하기 전에 스택이 비었는지 검사해야 한다.

시간·공간 복잡도

문자열을 한 번 순회하므로 시간 복잡도는 O(n)이다. 모든 문자가 여는 괄호이면 스택에 최대 n개가 쌓이므로 공간 복잡도는 O(n)이다.

3. 문제 해결 코드 (Python)

closing_to_opening은 닫는 괄호와 대응하는 여는 괄호를 연결한다. 여는 괄호는 스택에 저장하고, 닫는 괄호는 스택 top과 짝을 비교한다.

class Solution:
    def isValid(self, s: str) -> bool:
        closing_to_opening = {
            ")": "(",
            "]": "[",
            "}": "{",
        }
        stack = []

        for bracket in s:
            if bracket not in closing_to_opening:
                stack.append(bracket)
                continue

            if not stack or stack[-1] != closing_to_opening[bracket]:
                return False

            stack.pop()

        return not stack

닫는 괄호를 만났을 때 스택이 비었거나 top이 짝이 아니면 즉시 False를 반환한다. 마지막에 not stack을 반환해 여는 괄호가 모두 닫혔는지도 확인한다.

복사해 실행할 테스트

아래 assert를 풀이 코드와 같은 Python 파일에 붙여 실행하면 올바른 중첩, 종류 불일치, 미완성 괄호를 확인할 수 있다.

solver = Solution()
assert solver.isValid("()[]{}") is True
assert solver.isValid("([)]") is False
assert solver.isValid("((") is False

4. 공식 예제와 추가 검증

작성한 isValid 함수를 Python으로 실행해 공식 예제와 잘못된 순서·불완전한 괄호 사례를 확인했다.

공식 예제

입력	기대 출력	확인 결과
`"()"`	`True`	통과
`"()[]{}"`	`True`	통과
`"(]"`	`False`	통과
`"([])"`	`True`	통과
`"([)]"`	`False`	통과

추가 검증 1: 닫는 괄호가 먼저 등장

입력: s = ")()"
기대 출력: False
확인 결과: 통과
검증 목적: 비어 있는 스택에서 닫는 괄호가 나오는 즉시 거부하는지 확인

추가 검증 2: 끝까지 닫히지 않은 여는 괄호

입력: s = "(("
기대 출력: False
확인 결과: 통과
검증 목적: 입력을 모두 읽은 뒤 스택에 여는 괄호가 남는지 확인

추가 검증 3: 깊게 중첩된 서로 다른 괄호

입력: s = "{[()]}"
기대 출력: True
확인 결과: 통과
검증 목적: 서로 다른 괄호 종류가 올바른 LIFO 순서로 닫히는지 확인

5. 다른 풀이 방식 검색 및 비교

Valid Parentheses 공식 문제는 세 종류의 괄호가 올바른 순서와 짝으로 닫히는지 묻는다.
NeetCode의 Valid Parentheses 설명은 스택에 여는 괄호를 쌓고 닫는 괄호에서 짝을 검사하는 풀이를 설명한다.

모든 괄호 문자를 스택에 push한 뒤 닫는 괄호에서 pop해 비교할 수도 있다. 이 글에서는 닫는 괄호에 대응하는 여는 괄호를 바로 찾도록 딕셔너리를 사용했다. 두 방식 모두 각 괄호를 한 번씩 처리해 O(n) 시간과 O(n) 공간을 사용한다.

마무리

Valid Parentheses는 여는 괄호와 닫는 괄호의 개수뿐 아니라 종류와 중첩 순서까지 확인하는 문제다. 여는 괄호를 스택에 저장하고 닫는 괄호가 top과 짝을 이루는지 확인하면 LIFO 규칙으로 중첩을 검증할 수 있다.