[백준/Python] 괄호의 값 2504

알고리즘 분류 : 스택

시간복잡도 : O(N)

 

접근

• 계산이 끝난 경우(덧셈하는 경우)와 계속하는 경우(곱하는 경우)로 나누어서 접근해야한다
  예시)
  • 입력값 : ( ( ) [ [ ] ] ) ( [ ] )
  • 원래 계산 : (2+3*3)*2 + (2*3)
  • 바꾼 계산 : (2*2) + (2*3*3) + (2*3)
• 열린 괄호 (,[ 에서 실제 계산이 이루어지고,
  닫힌 괄호 ),] 에서 올바른 경우의 판단을 진행한다
• 올바른 경우의 판단은, stack[-1]이 아니라 string[cur_index-1]로 판단해야한다
  stack[-1]로 판단하면 계산이 중복된다

 

from sys import stdin
input = stdin.readline

def solution(string):
    result = 0
    cur_calc = 1
    stack = []
    # stack쌓기
    for i in range(len(string)):
        s = string[i]
        # (나 [인 경우
        if s == '(': 
            cur_calc *= 2
            stack.append(s)
        elif s == '[':
            cur_calc *= 3
            stack.append(s)
        # ),]의 경우
        elif s == ')':
            # stack이 비어있거나, 짝이 맞지 않은 경우
            if not stack or stack[-1] != '(': 
                return 0
            # 올바른 경우 ('()'인 경우)
            if string[i-1] == '(':
                result += cur_calc
            cur_calc //= 2
            stack.pop()
        else:
            # stack이 비어있거나, 짝이 맞지 않은 경우
            if not stack or stack[-1] != '[': 
                return 0
            # 올바른 경우 ('[]'인 경우)
            if string[i-1] == '[':
                result += cur_calc
            cur_calc //= 3
            stack.pop()
            
    return result if not stack else 0        

    
print(solution(input().strip()))