[백준 2024/09/11] 2504번 괄호의 값

1. 문제

https://www.acmicpc.net/problem/2504

 

2. 접근 방법

이번 문제는 올바른 괄호 찾기 + 분할 정복에 대한 적용을 필요로 하는 문제 같았다.

2개의 stack을 사용하여 이번 문제를 해결하였다.

 

괄호들이 처음 포함 된 stack을 b_stack 하나씩, pop하여 저장해 줄 stack을 a_stack이라고 선언하였다.

만약, b_stack에서 pop 된 녀석이 ) 또는 ] 라면, a_stack에 append 해주었다.

그 외 ( 또는 [ 을 만나게 된다면, 3개의 경우로 나누어서 판단하였다.

1. a_stack[-1] 이 짝이 맞게 ) 을 반환하는 경우
2. a_stack[-1] 이 짝이 만제 ] 을 반환하는 경우
3. a_stack[-1] 이 숫자를 반환하는 경우

1번의 경우엔, )을 pop 하여 a_stack에서 제거해 주었으며, a_stack.append(2)를 해주었다.

2번의 경우엔, ]을 pop 하여 a_stack에서 제거해 주었으며, a_stack.append(3)을 해주었다.

3번의 경우엔 ) 또는 ] 이 나올 때까지, pop을 하여, nums 리스트에 추가해 주었으며,

) 또는 ] 을 만나게 된다면 각각 2*sum(nums), 3*sum(nums) 를 a_stack 에 추가해 주었다.

 

또한, stack이 비어있는데, 참조하지 않도록 조심하였다.

 

3. 코드

def compute(b_stack):
    a_stack = []

    while b_stack:
        popped = b_stack.pop()

        if popped == ')' or popped == ']':
            a_stack.append(popped)

        else:
            if popped == '[' and a_stack and a_stack[-1] == ']':
                a_stack.pop()
                a_stack.append(3)

            elif popped == '(' and a_stack and a_stack[-1] == ')':
                a_stack.pop()
                a_stack.append(2)

            elif a_stack and isinstance(a_stack[-1], int):
                nums = [a_stack.pop()]

                while a_stack and isinstance(a_stack[-1], int):
                    nums.append(a_stack.pop())

                if a_stack and a_stack[-1] == ')' and popped == '(':
                    a_stack.pop()
                    a_stack.append(2*sum(nums))

                elif a_stack and a_stack[-1] == ']' and popped == '[':
                    a_stack.pop()
                    a_stack.append(3*sum(nums))
                else:
                    return 0

            else:
                return 0

    for s in a_stack:
        if not isinstance(s, int):
            return 0

    return sum(a_stack)


if __name__ == "__main__":
    b_stack = list(input())
    print(compute(b_stack))