[Python] 백준 2504 괄호의 값

1. 백준 2504 괄호의 값

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

 

💡 알고리즘 - 구현, 스택

- 보통 올바른 괄호 같이 앞의 원소와 짝지어서 올바른 조합인지 확인하는 문제는 스택을 쓴다. 여는 괄호 (, [는 append, 닫는 괄호 ), ]를 pop 해서 올바른 괄호인지 확인하는 방식이다.

 

✅ 풀이

stack = []
answer = 0
str = input()
flag = False
temp = 1

for i, w in enumerate(str):
  if w == "(":
    stack.append(w)
    temp *= 2
  elif w == "[":
    stack.append(w)
    temp *= 3
  elif w == ")":
    if not stack or stack[-1] == "[":
      flag = True
      break

    if str[i-1] == "(":
      answer += temp
    stack.pop()
    temp //= 2
  else:
    if not stack or stack[-1] == "(":
      flag = True
      break
    if str[i-1] == "[":
      answer += temp
    stack.pop()
    temp //= 3

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

 

예제를 통해 이해해보자.

(()[[]]]) 를 풀어쓰면 2*(2 + 3 * 3) = 22 이다. 그리고 이를 단계별로 시뮬레이션 해보면 다음과 같다.

(	temp = 1 * 2 = 2	( x )은 x * 2이므로 곱하기 2
(	temp = 2 * 2 = 4	동일
)	answer = 4 temp = 4 // 2 = 2	직전이 ( 이므로 괄호가 닫혔으니 더해주고, 그 다음 괄호를 받아 계산하기 위해 2를 나누어 원상복구
[	temp = 2 * 3 = 6	[ x ] 은 x * 3이므로 곱하기 3
[	temp = 6 * 3 = 18	동일
]	answer = 4+ 18 = 22 temp = 18 // 3 = 6	직전이 [ 이므로 괄호가 닫혔으니 더해주고, 그 다음 괄호를 받아서 더하기 위해 3를 나누어 원상복구
]	temp = 6 // 3 = 2	직전이 ] 이므로 괄호가 닫힌게 아니라서, 더하지 않고 3으로 나누어 원상복구
)	temp = 2 // 1 = 1	직전이 ] 이므로 괄호가 닫힌게 아니라서, 더하지 않고 2으로 나누어 원상복구

 

즉 괄호가 열리면 temp에 괄호의 종류에 따라 2 혹은 3을 곱해주고,

괄호가 닫힌 경우 덧셈으로 전환해야하므로 answer에 더한다. 이 때 짝이 맞지 않으면 이후 계산을 더 진행해야해서 더하지 않는다.