[BOJ] 2504 괄호의 값

2504 괄호의 값

1. 재귀

import sys
input = sys.stdin.readline

s = list(input().rstrip())[::-1]

def cal(start):
    r = 0
    while s:
        a = s.pop()
        if a == "(" or a == "[":
            r += cal(a) # 다음 괄호를 입력받아 처리한다.
        elif start == "(" and a == ")":
            return 2 * max(1,r)
        elif start == "[" and a == "]":
            return 3 * max(1,r)
    
    # 리스트가 비었는데 최종 return 하지 못했다는 것은 괄호에 문제가 있음을 의미
    print(0)
    sys.exit()

ans = 0    
while s:
    ans += cal(s.pop())
print(ans)

2. 스택

bracket = list(input())

stack = []
answer = 0
tmp = 1

for i in range(len(bracket)):

    if bracket[i] == "(":
        stack.append(bracket[i])
        tmp *= 2

    elif bracket[i] == "[":
        stack.append(bracket[i])
        tmp *= 3

    elif bracket[i] == ")":
        if not stack or stack[-1] == "[":
            answer = 0
            break
        if bracket[i-1] == "(":
            answer += tmp
        stack.pop()
        tmp //= 2

    else:
        if not stack or stack[-1] == "(":
            answer = 0
            break
        if bracket[i-1] == "[":
            answer += tmp

        stack.pop()
        tmp //= 3

if stack:
    print(0)
else:
    print(answer)

1. 열린 괄호
   1. 스택에 넣기
   2. ( 가 열리면 2를 곱해주고, [이 열리면 3을 곱해준다.
2. 닫힌 괄호
   1. 스택의 top 꺼내서 쌍 맞추기
      1. 틀리다면 0 출력
      2. 값 저장하기
         • 직전 괄호가 쌍이 맞는 경우에만 곱하기!
      3. 해당 값 //n을 해서 원래대로 값을 되돌린다.

[참고]

• https://my-coding-notes.tistory.com/343
• https://hongcoding.tistory.com/114

22.2.3