[python] 2504: 괄호의 값 코드 및 설명

2504: 괄호의 값

10개의 게시글을 보았는데 스택에 숫자와 문자(, ), [, ]가 모두 들어간 풀이들이 있었다. 하나의 Array에는 하나의 타입만 들어가야 한다고 생각해서 이런 방식을 습득하지 않았다.

아래의 코드에는 스택에 괄호만 들어간다.

접근법

예제 1번에 있는 (()[[]])([])을 계산할 때 우리는 $2*(2+3*3)+2*3$을 한다. 분배법칙을 사용하여 이 수식을 풀어보면 $2*2+2*3*3+2*3$이 된다.

코드 순서

1. 괄호 문제를 스택을 활용해서 풀 때는 여는 괄호가 나오면 stack에 append한다. 여기서는 괄호의 값을 계산하기 위해서 innerValue에 값을 곱한다. 처음에 보면 이걸 대체 왜 하는 건지 의문이 든다🤔 일단 괄호를 열었기 때문에 안에 다른 괄호가 있을 것을 예상하고 행하는 것이다.
2. 닫는 괄호가 나왔을 때는 (1) 짝이 맞는지 확인한 후에 (2) 계산해야 한다.
   • pop을 해야 하는데 stack이 비어있거나, stack에는 (와 [만 있는데 짝이 안 맞을 때는 return 0을 한다.
   • 짝이 맞으니 이제 계산하면 된다. ()나 []라면 innerValue를 result에 더한다. 또 여기서 2나 3을 더해야 할 거 같은데 왜 하는 건지 의문이 든다🤔 여기서 innerValue의 값을 이해하기 위해서는 (()...일 때를 생각해보면 좋다. 안에 있는 ()의 값은 $2*2$가 된다. 여는 괄호에서 곱해준 값을 여기서 쓰는 것이다.
   • 결론적으로 계산은 ()나 []처럼 쌍이 맞을 때만 하는 것이다.
   • innerValue //= 2나 3은 괄호를 닫았다는 뜻이다. 예를 들면 ((())) 이럴 때, 닫는 괄호를 지나갈 때마다 innerValue의 값이 줄어들어야 한다는 것을 알 수 있다.

코드

import sys
input = sys.stdin.readline


def checkBalence(bracket: str) -> int:
    result = 0
    innerValue = 1
    bracketStack = []

    for index in range(len(bracket)):
        if bracket[index] == "(":
            bracketStack.append("(")
            innerValue *= 2
        elif bracket[index] == "[":
            bracketStack.append("[")
            innerValue *= 3
        elif bracket[index] == ")":
            if not bracketStack or bracketStack[-1] != "(":
                return 0
            if bracket[index-1] == "(":
                result += innerValue
            bracketStack.pop()
            innerValue //= 2
        else:
            if not bracketStack or bracketStack[-1] != "[":
                return 0
            if bracket[index-1] == "[":
                result += innerValue
            bracketStack.pop()
            innerValue //= 3

        # print(
        #     f"result: {result} innerValue: {innerValue} stack {bracketStack}")

    if not bracketStack:
        return result
    return 0


inputBracket = input().rstrip()
print(checkBalence(inputBracket))

참고 링크

바킹독