[Gold V]
https://www.acmicpc.net/problem/2504
2504번: 괄호의 값
4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X
www.acmicpc.net
풀이
기본적으로, 문제를 보자마자 Stack을 활용해 풀어야겠다고는 생각이 들었다.
처음에는 단순하게 닫을 때마다 x2, x3을 해 주면 될 것이라고 생각했는데,
보다 보니 금방 (()[]) 같은 경우, 안에서 더해준 다음 밖에서 한 번에 곱해줘야 한다는 것을 알았다. ((2+3)x2)
따라서, Stack에 숫자를 같이 넣는 형식으로 생각하여 풀이하였다.
여는 괄호일 때는 항상 stack에 push한다.
닫는 괄호일 때, stack에서 닫는 괄호 쌍
"[" or "("가 나올 때 까지 pop한다.2-1. 만약 숫자가 나온다면, temp에 더해 놓고 continue.
숫자가 나왔을 때, deq에 남아있는 것이 없다면, 올바른 입력이 아니므로print(0).2-2. 문자가 나왔을 때, 닫는 괄호 쌍이 아니라면 올바른 입력이 아니므로
print(0)
닫는 괄호 쌍이라면,- temp == 0일 시, 바로 닫는 괄호 쌍이 나온 것이므로, stack에 2 or 3을 push.
- temp != 0일 시, 숫자가 나온 이후 괄호 쌍이 나왔으므로, temp의 숫자에 2 or 3을 곱하여 stack에 push.
반복을 종료한 후, stack에 문자가 남아 있다면 올바른 입력이 아니므로,
print(0)
숫자만 있다면, 모든 숫자를 더한 후 출력.
from collections import deque
s = input()
s = deque(list(s))
deq = deque()
result = 0
for i, p in enumerate(s):
# 여는 괄호
if p == "[" or p == "(":
deq.append(p)
# 닫는 괄호
else:
if not deq:
print(0)
exit()
if p == "]":
temp = 0
# 여는 괄호 '['가 뽑힐 때 까지 Pop하며, 숫자들을 더함.
while deq:
a = deq.pop()
# 숫자인 지 확인
if isinstance(a, int):
temp += a
# 여는 괄호가 없었다면, break.
if not deq:
print(0)
exit()
else:
# 다른 괄호가 나오면, break.
if a != "[":
print(0)
exit()
# 여는 괄호 뒤 바로 닫는 괄호라면, 3을 더하고 끝냄. 숫자가 나왔다면, 나온 숫자에 3을 곱해 더하고 끝냄.
if temp == 0:
temp = 3
else:
temp *= 3
break
deq.append(temp)
else: # p == ")"
temp = 0
# 여는 괄호 '('가 뽑힐 때 까지 Pop하며, 숫자들을 더함.
while deq:
a = deq.pop()
# 숫자인 지 확인
if isinstance(a, int):
temp += a
# 여는 괄호가 없었다면, break.
if not deq:
print(0)
exit()
else:
# 다른 괄호가 나오면, break.
if a != "(":
print(0)
exit()
# 여는 괄호 뒤 바로 닫는 괄호라면, 3을 더하고 끝냄. 숫자가 나왔다면, 나온 숫자에 3을 곱해 더하고 끝냄.
if temp == 0:
temp = 2
else:
temp *= 2
break
deq.append(temp)
# deq 내에 괄호가 남아 있다면, print(0)
for k in deq:
if not isinstance(k, int):
print(0)
exit()
print(sum(deq))