Valid Parentheses

Q: 유효한 괄호의 시간 복잡도는 무엇인가요?

스택 솔루션은 각 문자가 최대 한 번 푸시되거나 팝되므로 O(n) 시간에 실행됩니다. 최악의 경우, 여는 문자만 있는 문자열에서는 O(n) 공간을 사용합니다. 짝이 맞는 쌍을 반복해서 제거하는 방법은 깊게 중첩된 문자열에서 한 번에 한 쌍만 제거되므로 O(n²) 시간이 걸립니다.

쉬움스택

+10

괄호 문자 (, ), [, ], { 및 }로만 이루어진 문자열 s가 주어집니다. 괄호가 균형을 이루면 true를 반환하세요. 즉, 각 닫는 괄호가 아직 열려 있는 가장 최근 괄호를 닫고, 두 괄호의 종류가 같으며, 끝에 열린 괄호가 남아 있지 않아야 합니다. 그렇지 않으면 false를 반환하세요.

함수

isValid(s: string) → boolean

sstring: 확인할 괄호 문자열
반환값boolean: 괄호가 균형을 이루는지 여부

제약 조건

1 ≤ s.length ≤ 10⁴
s에는 (, ), [, ], { 및 } 문자만 포함되어 있습니다.

예제

입력: s = "[]{}()"
출력: true
설명: 세 쌍이 나란히 서 있으며, 각 쌍은 열린 직후에 닫힙니다.

입력: s = "{(})"
출력: false
설명: }는 그 뒤에 열린 (가 아직 닫히지 않은 상태에서 나오므로, 잘못된 종류의 괄호를 닫습니다.

후속 질문

문자열에 소괄호만 들어 있다면, 스택 대신 카운터 하나만 사용해 추가 공간 O(1)로 확인할 수 있을까요?

풀이

괄호의 개수를 세는 것만으로는 충분하지 않습니다. {(})에는 여는 괄호와 닫는 괄호가 각각 하나씩 있지만, 순서가 중요하기 때문에 여전히 잘못된 문자열입니다. 스택은 아직 닫히지 않은 괄호를 열린 순서대로 보관하므로, 스택을 사용해 한 번만 순회하면 문자열 전체를 판별할 수 있습니다.

일치하는 쌍을 반복해서 제거하기

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

모든 균형 잡힌 문자열에는 괄호 사이에 아무것도 없는 가장 안쪽 쌍이 있습니다. 예를 들어 {[()]} 안의 ()가 그렇습니다. 서로 인접한 짝을 이룬 쌍을 삭제해도 문자열의 균형 여부는 바뀌지 않습니다. 그러므로 한 번의 삭제로 아무것도 제거되지 않을 때까지 삭제를 반복하세요. 균형 잡힌 문자열은 빈 문자열로 줄어들고, 균형이 맞지 않는 문자열은 처음부터 {(})처럼 문자가 남은 채 더 이상 줄어들지 않습니다.

각 라운드에서는 문자열 전체를 훑으며 새로운 복사본을 만들고, (((...)))와 같은 중첩 문자열은 라운드마다 쌍 하나씩 없어집니다. 최대 n/2번의 라운드가 필요하며, 각 라운드의 작업량은 O(n)이므로 전체적으로는 O(n²)입니다.

알고리즘

문자열에서 모든 (), [] 및 {}를 삭제합니다.
이번 단계에서 삭제된 것이 없다면 중단합니다.
그렇지 않으면 더 짧아진 문자열로 반복합니다.
문자열이 비어 있으면 true를 반환하고, 괄호가 하나라도 남아 있으면 false를 반환합니다.

def isValid(s):
    while True:
        # Delete every adjacent matched pair in one round.
        shorter = s.replace("()", "").replace("[]", "").replace("{}", "")
        if shorter == s:
            break  # nothing left to delete
        s = shorter
    return s == ""

스택을 사용한 한 번의 순회

핵심 아이디어

닫는 괄호는 아직 열려 있는 괄호 중 가장 최근에 열린 괄호를 닫아야 합니다. 마지막에 들어간 괄호가 먼저 닫히며, 이러한 후입선출 순서를 스택이 정확히 구현합니다.

각 여는 괄호가 기다리는 닫는 괄호를 스택에 넣습니다. 그런 다음 닫는 괄호는 스택의 맨 위 항목과 일치해야 합니다. 스택이 비어 있으면 닫을 괄호가 없는 것이고, 맨 위 항목이 다르면 잘못된 종류의 괄호를 닫는 것입니다. )가 맨 위에 있을 때 {(})의 }가 그런 경우입니다. 마지막에 스택에 남아 있는 항목은 ((에서처럼 열렸지만 닫히지 않은 괄호입니다. 각 문자는 한 번씩 스택에 들어가거나 빠집니다. 시간 복잡도는 O(n)이며, 스택에는 최대 n개의 항목이 들어갑니다.

알고리즘

빈 스택을 만듭니다.
여는 괄호가 나오면 이에 대응하는 닫는 괄호를 푸시합니다.
닫는 괄호가 나오면 스택이 비어 있거나 스택의 맨 위 문자가 다른 경우 false를 반환하고, 그렇지 않으면 팝합니다.
마지막 문자를 처리한 후 스택이 비어 있는 경우에만 true를 반환합니다.

def isValid(s):
    closers = {'(': ')', '[': ']', '{': '}'}
    stack = []
    for ch in s:
        if ch in closers:
            stack.append(closers[ch])
        elif not stack or stack.pop() != ch:
            return False
    return not stack

함정과 경계 사례

각 종류의 괄호 개수를 세는 것. {(})는 괄호 개수가 서로 맞지만 여전히 올바르지 않고, )(는 순서만으로도 유효하지 않습니다.
빈 스택에서 꺼내는 것. }나 )]}처럼 닫는 괄호로 시작하는 문자열은 오류가 발생하는 대신 false를 반환해야 합니다.
마지막 검사를 건너뛰는 것. (([{는 잘못된 닫는 괄호를 만나지 않으므로, 남아 있는 스택만이 올바르지 않음을 보여 줍니다.
길이를 믿는 것. 홀수 길이는 항상 유효하지 않지만, 짝수 길이라고 해서 유효하다는 뜻은 아닙니다. (]와 ())(는 모두 유효하지 않습니다.
제거 방식에서 괄호를 이스케이프하지 않고 정규식이나 Lua 패턴에 전달하는 것. (와 [는 그 안에서 특별한 의미를 가집니다. 일반 텍스트 치환을 사용하세요.

자주 묻는 질문3

유효한 괄호의 시간 복잡도는 무엇인가요?

스택 솔루션은 각 문자가 최대 한 번 푸시되거나 팝되므로 O(n) 시간에 실행됩니다. 최악의 경우, 여는 문자만 있는 문자열에서는 O(n) 공간을 사용합니다. 짝이 맞는 쌍을 반복해서 제거하는 방법은 깊게 중첩된 문자열에서 한 번에 한 쌍만 제거되므로 O(n²) 시간이 걸립니다.

유효한 괄호를 확인할 때 스택을 사용하는 이유는 무엇인가요?

괄호는 중첩되므로 마지막에 열린 괄호가 가장 먼저 닫혀야 합니다. 스택을 사용하면 해당 괄호가 맨 위에 놓이므로 상수 시간에 읽고 제거할 수 있으며, 이를 통해 전체 검사를 O(n)으로 유지할 수 있습니다.

빈 문자열도 유효한 괄호 문자열인가요?

네. 빈 문자열에는 짝이 맞지 않는 괄호가 없으므로 균형이 맞습니다. 스택은 비어 있고 제거 루프에서 제거할 항목도 없습니다. 이 문제에서 s에는 항상 문자가 하나 이상 있습니다.

def isValid(s):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자

s = "[]{}()"

예상 출력

true