[리트코드 856] 괄호 문자열 점수 — 깊이에 따른 기여 합산

원제: Score of Parentheses

문제 요약

균형 잡힌 괄호 문자열 s의 점수를 계산해 정수로 반환합니다. ()의 점수는 1이고, 이어 붙인 문자열은 점수를 더하며, 한 겹 감싼 문자열은 내부 점수의 2배입니다.

조건과 입출력

2 <= s.length <= 50이며 s는 (와 )만으로 이루어진 균형 잡힌 괄호 문자열입니다. 반환값은 규칙에 따라 계산한 점수입니다.

예제와 문제 자료

예제 1: s = "()"이면 출력은 1입니다. 예제 2: s = "(())"이면 출력은 2입니다. 각각 가장 안쪽의 ()가 기여하는 점수는 1이고, 바깥 괄호 한 겹은 그 점수를 2배로 만듭니다.

풀이 아이디어

stack에는 아직 닫히지 않은 여는 괄호를 저장하므로, 닫는 괄호를 처리한 뒤의 len(stack)은 현재 괄호 쌍 바깥에 남아 있는 괄호의 수입니다. s[i-1] == "("일 때 현재 쌍은 바로 ()이므로 기본 점수 1을 새로 더하면 됩니다. 이 쌍이 바깥 괄호 d겹 안에 있으면 각 겹이 점수를 두 배로 하므로 기여분은 2 ** d입니다. 반면 내부가 더 복잡한 쌍은 그 안의 가장 안쪽 ()들이 이미 해당 깊이에 맞는 기여분으로 합산됩니다. 따라서 닫는 괄호마다 바로 안쪽이 ()인 경우만 더하면 중복 계산 없이 전체 점수를 얻습니다.

코드의 핵심

answer는 지금까지 더한 점수이고, stack의 길이는 현재 열린 괄호의 중첩 깊이를 나타냅니다. x == "("이면 여는 괄호를 쌓습니다. 그 외에는 균형 문자열의 닫는 괄호이므로 stack.pop()으로 대응하는 여는 괄호를 제거한 뒤 점수 조건을 확인합니다.

()에서는 닫는 괄호 처리 후 깊이가 0이고, 직전 문자가 (이므로 answer += 2 ** 0이 실행되어 결과는 1입니다. (())에서는 안쪽 ()를 닫을 때 깊이가 1이어서 2를 더합니다. 바깥 괄호를 닫을 때는 직전 문자가 )이므로 추가하지 않아 결과는 2입니다. 이는 안쪽 점수 1이 바깥 괄호에 의해 두 배가 된 값입니다.

제출 코드

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        stack = []
        answer = 0
        for i,x in enumerate(s):
            if x == "(":
                stack.append("(")
            else:
                stack.pop()
                if s[i-1] == "(":
                    answer += 2 ** len(stack)

        return answer

복잡도

n = len(s)라 하면 각 문자를 한 번씩 처리하고 스택 연산은 상수 시간이라 시간 복잡도는 O(n)입니다. stack은 최악에 n/2개의 여는 괄호를 담으므로 보조 공간은 O(n)입니다. answer와 반환값은 정수 하나이므로 결과 저장 공간은 O(1)입니다.

복습 포인트

코드는 입력이 균형 잡혀 있다는 원문 조건에 의존해 닫는 괄호마다 stack.pop()을 수행합니다. s[i-1] 검사는 현재 괄호 쌍이 정확히 ()인지 판별하며, 중첩된 쌍의 점수는 깊이를 반영한 2 ** len(stack)으로 처리합니다.

출처

문제 원문