문제 설명

Valid Parentheses - LeetCode

해설

문제 설명

주어진 문자열 s가 유효한 괄호 문자열인지 확인하는 문제입니다.
문자열에는 다음과 같은 괄호만 포함될 수 있습니다.

  • () (소괄호)
  • {} (중괄호)
  • [] (대괄호)

✅ 유효한 괄호 문자열의 조건:

  1. 열린 괄호는 반드시 닫힌 괄호와 짝을 이뤄야 함
  2. 닫힌 괄호가 열린 괄호보다 먼저 나오면 안 됨
  3. 괄호의 순서가 올바르게 짝을 이뤄야 함

예제

예제 1

1

s = "()"

🔹 출력: True (괄호가 올바르게 닫힘)

예제 2

1

s = "()[]{}"

🔹 출력: True (괄호 쌍이 모두 유효함)

예제 3

1

s = "(]"

🔹 출력: False ((는 )로 닫혀야 하지만 ]가 나옴)

예제 4

1

s = "{[]}"

🔹 출력: True (중첩된 올바른 괄호)

예제 5

1

s = "([)]"

🔹 출력: False (()와 []가 교차되어 유효하지 않음)

접근 방법 (스택 활용)

핵심 아이디어:

  • 스택(Stack) 자료구조를 활용하여 열린 괄호를 저장하고, 닫힌 괄호가 나오면 스택의 마지막 요소와 짝을 맞추는 방식으로 해결

풀이 과정

  1. 괄호 매칭을 위한 딕셔너리 생성
1

matching = {')': '(', '}': '{', ']': '['}
  1. 스택을 사용하여 열린 괄호 저장
    • 열린 괄호는 스택에 push()
  2. 닫힌 괄호가 나오면 스택의 top과 비교
    • 스택이 비었거나, pop()한 값과 다르면 False
  3. 모든 괄호 처리 후 스택이 비어 있어야 True

시간 복잡도 분석

연산시간 복잡도설명
push()O(1)열린 괄호 추가
pop()O(1)닫힌 괄호 매칭 시 제거
전체 반복문O(N)문자열 길이 N만큼 반복

전체 시간 복잡도: O(N)
공간 복잡도: O(N) (스택 사용)

추가 최적화

문자열 길이가 홀수이면 무조건 False

1
2

if len(s) % 2 == 1:
    return False

✅ 열린 괄호가 없을 때 닫힌 괄호가 나오면 즉시 False
✅ 닫힌 괄호는 반드시 열린 괄호와 짝을 맞춰야 함

코드 풀이

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def isValid(s: str) -> bool:
    stack = []
    matching = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in matching:  # 닫힌 괄호일 경우
            if not stack or stack.pop() != matching[char]:
                return False
        else:  # 열린 괄호일 경우
            stack.append(char)

    return not stack  # 스택이 비어 있으면 True

Javascript

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

var isValid = function(s) {
    let stack = [];
    let matching = {')': '(', '}': '{', ']': '['};

    for (let char of s) {
        if (matching[char]) { // 닫힌 괄호일 경우
            if (stack.length === 0 || stack.pop() !== matching[char]) {
                return false;
            }
        } else { // 열린 괄호일 경우
            stack.push(char);
        }
    }

    return stack.length === 0; // 스택이 비어 있으면 True
};

참고 및 출처

programmers Coding Test
LeetCode - The World’s Leading Online Programming Learning Platform