[Python] BOJ 2504 괄호의 값

요구사항 

• 시간 제한 1초 
  • N 의 값은 크지 않다. N <= 30 어떤 알고리즘을 써도 무방하지만 스택 밖에 생각이 안난다. 
• 메모리 제한 128MB 
  • 128MB 현재 수준에서 충분
• 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력한다. 만약 올바른 괄호열이 아닐 시 0을 출력한다.

설계

• 누적된 곱을 저장할 변수를 1로 초기화한다.
• 누적할 값을 더할 변수를 0으로 초기화한다.
• 스택을 초기화한다.
• 입력 받은 문자열을 for문을 돌려서 확인할 것.
  • 이 때 문자를 순회하며 크게 4가지로 나눈다.
  •  문자 == '(' 일 때
    • 스택.append('()
    • 누적할 곱 *= 2    # 그 이유는 이제 닫혔으니깐 누적된 곱을 좀 빼줘야지. 
  • 문자 == '[': 일 때
    • 스택.append('[')
    • 누적할 곱 *3
  • 문자 == ')' 일 때 
    • 만약 스택이 비어있거나 스택의 peak가 '(' 이 아닐 때 
      • 0을 반환한다.
    • 만약 현재 순회하는 문자의 -1 이 '(' 일 때 
      • 누적할 값을 더할 변수에 += 누적된 곱
    • 스택.pop()
    • 누적된 곱 //= 2
  • 문자 ==']' 일 때 위와 동일

구현

import sys
input = lambda: sys.stdin.readline().strip()

def calculate(s):
    sum = 0
    multi = 1
    stack = []

    for i in range(len(s)):
        if s[i] == '(':
            multi *= 2
            stack.append('(')
        elif s[i] == '[':
            multi *= 3
            stack.append('[')
        elif s[i] == ')':
            if not stack or stack[-1] != '(':
                return 0
            if s[i - 1] == '(':
                sum += multi
            stack.pop()
            multi //= 2
        elif s[i] == ']':
            if not stack or stack[-1] != '[':
                return 0
            if s[i - 1] == '[':
                sum += multi
            stack.pop()
            multi //= 3
            
    return sum if not stack else 0  #스택이 비어있을 경우 sum을 반환 그렇지 않으면 0을 반환

if __name__ == "__main__":
    line = input()
    print(calculate(line))