[리트코드 678] 유효한 괄호 문자열 — 양방향 균형 검사

원제: Valid Parenthesis String

문제 요약

문자열 s의 *는 (, ), 빈 문자열 중 하나로 해석할 수 있습니다. 이 선택으로 괄호 규칙을 만족시킬 수 있으면 True, 아니면 False를 반환합니다.

조건과 입출력

s에는 (, )와 *만 들어가며, 길이는 1 <= s.length <= 100입니다. 여는 괄호와 닫는 괄호는 짝을 이루어야 하고, 여는 괄호가 대응하는 닫는 괄호보다 앞서야 합니다. 원문 예제: s = "()" → true, s = "(*)" → true, s = "(*))" → true, s = "(" → false.

예제와 문제 자료

예제 2의 "(*)"에서는 *를 빈 문자열로 보면 ()가 되어 유효합니다. 예제 4의 "("는 닫는 괄호가 없으므로 유효하지 않습니다.

풀이 아이디어

*의 세 가지 선택을 모두 만들 필요 없이, 두 방향에서 균형이 깨지는지만 확인합니다. 왼쪽부터 검사할 때 *를 여는 괄호로 볼 수 있으므로, 지금까지 닫는 괄호가 여는 괄호 후보보다 많아지는 경우만 실패입니다. 오른쪽부터 검사할 때는 반대로 *를 닫는 괄호로 볼 수 있습니다. 두 검사 모두 통과하면 앞쪽의 닫는 괄호 부족과 뒤쪽의 여는 괄호 부족이 각각 해소될 수 있어 유효한 해석이 존재합니다.

코드의 핵심

첫 번째 순회는 for x in s입니다. x == ")"이면 cnt를 줄이고, 그 외(( 또는 *)에는 늘립니다. 따라서 cnt < 0이면 지금까지의 닫는 괄호를 감당할 여는 괄호 후보가 부족해 즉시 False를 반환합니다.

두 번째 순회는 for x in reversed(s)입니다. x == "("이면 cnt를 줄이고, 그 외() 또는 *)에는 늘립니다. 이때 cnt < 0이면 뒤에서부터 보아도 여는 괄호가 닫는 괄호 후보보다 많아 이를 대응시킬 수 없으므로 False입니다. 두 순회가 모두 통과하면 True입니다.

예제 s = "(*))"의 코드 추적: 왼쪽부터 cnt는 (에서 1, *에서 2, )에서 1, 마지막 )에서 0이므로 실패하지 않습니다. 오른쪽부터는 )에서 1, )에서 2, *에서 3, (에서 2가 되어 역시 실패하지 않고 True를 반환합니다.

제출 코드

class Solution:
    def checkValidString(self, s: str) -> bool:
        cnt = 0
        for x in s:
            if x == ")":
                cnt -= 1
            else:
                cnt += 1
            
            if cnt < 0:
                return False

        cnt = 0
        for x in reversed(s):
            if x == "(":
                cnt -= 1
            else:
                cnt += 1

            if cnt < 0:
                return False

        return True

복잡도

문자열 길이를 n이라 하면 두 번 순회하므로 시간 복잡도는 O(n)입니다. cnt 외에 길이에 비례하는 보조 자료를 만들지 않으므로 보조 공간은 O(1)입니다. 결과는 불리언 하나입니다.

복습 포인트

*를 한 번의 순회에서 항상 특정 괄호로 고정하는 것이 아니라, 두 방향 검사에서 서로 다른 역할을 할 수 있는 후보로 취급합니다. 입력 길이는 최소 1이므로 빈 문자열은 제약에 포함되지 않습니다.

출처

문제 원문