[stack] 2504번 괄호의 합

백준 2504번 괄호의 합 링크 : 

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

2504번: 괄호의 값

2504번 문제 설명

괄호의 합은 두 가지 로직이 필요한 문제였다. 

 

    - 괄호가 잘 닫혀있는 지 확인

    - 괄호의 합을 계산

 

괄호가 잘 닫혀있는 지 확인 (불가능한 형태인지 확인)

    - Stack을 사용하여 연 괄호 '(', '['를 닫는 괄호 ')', ']'로 전부 잘 닫히는 지 확인한다.

        -> 연 괄호일 때 push, 닫는 괄호 일 때 stack top 괄호 모양 확인 후 pop

        -> 닫는 괄호와 연 괄호가 매칭되지 않으면 불가능한 형태이다. 중지하고 0을 출력한다.

        -> input string을 전부 탐색한 후에 stack이 비어있지 않으면 (잘 닫힌 것이 아니면) 불가능으로 판단

 

    - 여는 괄호의 갯수와 닫는 괄호의 갯수를 확인한다.

        -> 이 부분 때문에 조금 애먹었다.

        -> '(((((()))' 왼쪽과 같은 여는, 닫는 괄호의 수가 일치하지 않은 경우를 감지하기 위해,

             (), [] 형태마다 변수를 두어 괄호의 수를 체크한다. 여는 괄호일 때는 +1, 닫는 괄호일 땐 -1

 

괄호의 합을 계산

    - 괄호의 합을 계산하기 위해서는 분배 법칙을 적용된 식을 이해해야 한다. (a x (b + c) = a x b + a x c)

 

    - 괄호 안에 괄호가 정의되는 경우와 괄호가 끝나 괄호끼리 +하는 경우를 위해 몇 가지 규칙이 필요하다.

         -> 괄호가 열리는 순간 depth가 깊어진다고 가정한다.

              ( () 모양 괄호는 x2 depth, [] 모양 괄호는 x3 depth )

         -> 괄호가 열린 후 바로 닫힐 때는 +를 수행한다. ')' 모양일 때 바로 전 모양이 '(' 이면 +를 수행하는 식

         -> 괄호가 닫히는 순간 depth를 하나 벗어난다고 본다.

              ( (X), '()' 모양의 괄호를 벗어나면 /2, '[]' 모양의 괄호를 벗어나면 /3 )

 

    - 규칙에 따라 적용하면 문제의 예시 앞부분은 다음과 같이 풀이 될 수 있다.

         -> 예시 : "(()[[]])" , 초기 값 depth = 1, 초기 값 sum = 0

         -> 0번째 ( : depth x 2                      || depth = 2, sum = 0, 전체에 x2를 한 상태와 같음

         -> 1번째 ( : depth x 2                      || depth = 4,  sum = 0

         -> 2번째 ) : sum += depth, depth / 2  || depth = 2,  sum = 4

         -> 3번째 [ : depth x 3                      || depth = 6,  sum = 4

         -> 4번째 [ : depth x 3                      || depth = 18, sum = 4

         -> 5번째 ] : sum += depth, depth / 3  || depth = 6,  sum = 22

         -> 6번째 ] : depth / 3                      || depth = 2,  sum = 22

         -> 7번째 ) : depth / 2                      || depth = 1,  sum = 22

         -> 최종 값 : 22

         -> 손으로 계산해본 "(()[[]])" 값과 같음! =>> 2 x (2 + (3x3)) = 4 + 18 = 22

 

 * 구현 코드

input_data = input()
# input_data = "(()[[]])([])"

class Stack(list):
    push = list.append    
    def is_empty(self):   
        if not self:
            return True
        else:
            return False

    def peek(self): 
        if self.is_empty():
            return ""
        else :
            return self[-1]

stack = Stack()

mul_depth = 1
total_sum = 0
impossible = 0
s = 0
l = 0
leng = len(input_data)

for idx in range(leng):
    brk = input_data[idx]
    if brk.__eq__("("):
        s += 1
        mul_depth = mul_depth * 2
        stack.push(brk)

    elif brk.__eq__("["):
        l += 1
        mul_depth = mul_depth * 3
        stack.push(brk)

    elif brk.__eq__(")"):
        s -= 1
        if not stack.peek().__eq__("("):
            impossible = 1
            break

        if input_data[idx-1].__eq__('('):
            total_sum += mul_depth
        
        mul_depth = mul_depth / 2
        stack.pop()

    elif brk.__eq__("]"):
        l -= 1
        if not stack.peek().__eq__("["):
            impossible = 1
            break

        if input_data[idx-1].__eq__('['):
            total_sum += mul_depth
        
        mul_depth = mul_depth / 3
        stack.pop()

if (stack.is_empty == 0) or impossible or l or s:
    print(0)
else :
    print(int(total_sum))