[LeetCode] 괄호의 점수 #Stack

닫힌 괄호 문자열 S가 주어지면 다음 규칙에 따라 문자열의 점수를 계산합니다:

• ()는 1점입니다.
• A와 B가 닫힌 괄호 문자열일 때, AB는 A+B점입니다.
• A가 괄호 문자열일 때, (A)는 2 * A점입니다.

Example 1:

Input: "()"

Output: 1

Example 2:

Input: "(())"

Output: 2

Example 3:

Input: "()()"

Output: 2

Example 4:

Input: "(()(()))"

Output: 6

Note:

1. S는 ( 와 ) 만을 포함하는 닫힌 괄호 문자열입니다.
2. 2 <= S의 길이 <= 50

나의 풀이

괄호 문제의 경우 스택으로 생각하고 풉니다. 문자열을 순회했을 때 문자가 ( 와 )인 경우가 있으며, ( 인 경우 스택에 집어넣고, ) 인 경우 뺍니다. 위 문제의 경우 스택에서 뺄 때 스택에 쌓인 ( 의 갯수를 세면 중첩 상태를 얻어 점수를 계산할 수 있습니다.

다만 (())와 같이 ) 다음에 )가 온 경우, 점수가 이미 계산된 상태이므로 pop만 해주었습니다. 시간 복잡도는 O(N), 공간 복잡도도 O(N)입니다.

class Solution:
    def scoreOfParentheses(self, S: str) -> int:
        stack = []; answer = 0; last = ''
        for i, c in enumerate(S):
            if c == '(':
                stack.append(i)
            elif last != ')' and c == ')':
                stack.pop()
                answer += 2 ** len(stack)
            else:
                stack.pop()
            last = c
            
        return answer

정답

LeetCode Solutions는 Divide and Conquer, Stack, Count Cores 세 가지 접근법을 제시하고 있습니다. 세 가지 접근법의 원리, 코드, 시간 및 공간 복잡도를 알아봅시다.

Approach 1: Divide and Conquer

문자열 S를 S = A + B로 분할합니다. 여기서 A와 B는 닫힌 괄호 문자열이고 A는 S의 가능한 가장 작은, 비어 있지 않은 부분 문자열입니다. 재귀를 통해 문자열을 분할합니다. 비어 있지 않은 두 개의 닫힌 문자열로 분할할 수없는 경우 return 합니다.

닫힌 상태를 추적하여 (= '(' 에서 ')' 수를 뺀 값 ) S를 원시 하위 문자열 S = P_1 + P_2 + ... + P_n으로 분할 할 수 있습니다. 그러면 정의에 따라 score (S) = score (P_1) + score (P_2) + ... + score (P_n)입니다.

각 기본 하위 문자열 (S [i], S [i + 1], ..., S [k])에 대해 문자열의 길이가 2이면이 문자열의 점수는 1입니다. 그렇지 않으면 부분 문자열 (S [i + 1], S [i + 2], ..., S [k-1]) 점수의 두 배입니다.

class Solution(object):
    def scoreOfParentheses(self, S):
        def F(i, j):
            #Score of balanced string S[i:j]
            ans = bal = 0

            # Split string into primitives
            for k in range(i, j):
                bal += 1 if S[k] == '(' else -1
                if bal == 0:
                    if k - i == 1:
                        ans += 1
                    else:
                        ans += 2 * F(i+1, k)
                    i = k+1

            return ans

        return F(0, len(S))

시간 복잡도는 O(N^2), 공간 복잡도는 O(N)입니다.

Approach 2: Stack

둘러쌓인 괄호의 개수에 따라 깊이를 정할 수 있습니다. 예를 들어, (()(@())) 문자열에서 @의 깊이는 2입니다. 우리의 목표는 현재의 깊이에서 점수를 유지하는 것입니다. 여는 괄호를 볼 때 깊이를 늘리고 새 깊이의 점수는 0입니다. 닫는 괄호를 볼 때는 이전 깊은 부분의 점수를 두 배 더합니다. 점수가 1 인 ()를 세는 경우는 예외입니다. 

예를 들어 (()(()))를 계산할 때 스택은 다음과 같습니다.

• [0, 0] after parsing (
• [0, 0, 0] after (
• [0, 1] after )
• [0, 1, 0] after (
• [0, 1, 0, 0] after (
• [0, 1, 1] after )
• [0, 3] after )
• [6] after )

class Solution(object):
    def scoreOfParentheses(self, S):
        stack = [0] #The score of the current frame

        for x in S:
            if x == '(':
                stack.append(0)
            else:
                v = stack.pop()
                stack[-1] += max(2 * v, 1)

        return stack.pop()

시간 복잡도는 O(N), 공간 복잡도도 O(N)입니다. 스택에 쓸모없는 괄호를 집어넣기보다 점수를 계산하는 용도로 활용하니 확실히 제 코드보다 훨씬 깔끔해졌네요.

Approach 3: Count Cores

점수를 산정하는 규칙에 따라, 최종 합은 2의 거듭 제곱의 합이됩니다. (LeetCode 설명은 그렇게 서술하고 있지만, 사실 모든 양의 정수가 그렇지 않나요????)

Approach 1에 쓰인 것처럼 문자열의 열고 닫힌 상태를 추적합니다. ( 다음에 )를 마주칠 때마다 1 << depth 값을 더합니다.

class Solution(object):
    def scoreOfParentheses(self, S):
        ans = bal = 0
        for i, x in enumerate(S):
            if x == '(':
                bal += 1
            else:
                bal -= 1
                if S[i-1] == '(':
                    ans += 1 << bal
        return ans

시간 복잡도는 O(N)이지만 공간 복잡도는 O(1)이 됩니다. 대신 머리가 좀 아프네요.

실제 실행 시간과 메모리는 다음과 같습니다. 위에서부터 접근법 1, 2, 3, 나의 풀이이며, 크게 차이나는 부분은 없네요. 런타임 에러는 무시하세요ㅎㅎ;