[스택큐] 괄호의 합 - 백준

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

2504번: 괄호의 값

 

스택큐 유형의 전형적인 문제인 연산자 관련 문제이다. 

 

본 문제에서는 괄호의 순서에 맞는 연산을 수행해야 하며 괄호를 형성하지 못하는 경우 0을 반환해야 한다.

 

( ) = 2

[ ] = 3

(..) = 2 * ..

[..] = 3 * ..

(..)[..] = (2 * ..) + (3 * ..)

다음과 같은 연산 성질을 갖는다. 

 

구체적으로 예를 들어 살펴보자

 

(()[[]])([])

 

다음은 알고리즘 Flow다 

 

Stack에 우선 추가

 if 여는 괄호의 경우 그냥 pass

 else 닫는 괄호의 경우는

   괄호를 형성하지 못하는 경우는 return 0

   괄호를 형성할 수 있는 경우

      if 바로 [ ], ( ) 를 구성하는 경우 3, 2를 stack에 추가

      else 바로는 형성을 못하는 경우 

        if 합을 계산할 수 있는 경우 -> 덧셈을 취해준 값을 넣어줌

        else 합을 계산할 수 없는 경우 -> 괄호를 형성할 수 없는 경우이므로 return 0

최종 Stack에 있는 남은 수들의 합을 구함

이 연산이 안되는 경우 return 0

 

구체적인 예제로 살펴보자

 

 

다음 그림과 같이 동작을 하게 된다.

 

최종 코드는 다음과 같다.

 

par = input()
stack = []

def solution(par, stack) :
    for p in par :
        stack.append(p)
        if p in [')', ']'] :
            if p == par[0] :
                return 0
            if p == ']' :
                stack.pop() # 닫는 괄호 뽑기
                nxt = stack.pop() # 여는 괄호인지 확인
                for_sum = []
                if nxt == '[' :
                    stack.append(3)
                else :
                    for_sum.append(nxt)
                    while True :
                        if stack == [] :
                            return 0
                        s = stack.pop()
                        for_sum.append(s)
                        if s == '[' :
                            for_sum.pop()
                            break
                    if  ('(' in for_sum ) or  (')' in for_sum ) :
                        return 0
                    stack.append(3*sum(for_sum))
            if p == ')' :
                stack.pop() # 닫는 괄호 뽑기
                nxt = stack.pop() # 여는 괄호인지 확인
                for_sum = []
                if nxt == '(' :
                    stack.append(2)
                else :
                    for_sum.append(nxt)
                    while True :
                        if stack == [] :
                            return 0
                        s = stack.pop()
                        for_sum.append(s)
                        if s == '(' :
                            for_sum.pop()
                            break
                    if  ('[' in for_sum ) or  (']' in for_sum ) :
                        return 0
                    stack.append(2*sum(for_sum))


    try :
        return sum(stack)
    except :
        return 0


print(solution(par,stack))