미소를뿌리는감자의 코딩
[백준 2024/09/11] 2504번 괄호의 값 본문
728x90
1. 문제
https://www.acmicpc.net/problem/2504
2. 접근 방법
이번 문제는 올바른 괄호 찾기 + 분할 정복에 대한 적용을 필요로 하는 문제 같았다.
2개의 stack을 사용하여 이번 문제를 해결하였다.
괄호들이 처음 포함 된 stack을 b_stack 하나씩, pop하여 저장해 줄 stack을 a_stack이라고 선언하였다.
만약, b_stack에서 pop 된 녀석이 ) 또는 ] 라면, a_stack에 append 해주었다.
그 외 ( 또는 [ 을 만나게 된다면, 3개의 경우로 나누어서 판단하였다.
- a_stack[-1] 이 짝이 맞게 ) 을 반환하는 경우
- a_stack[-1] 이 짝이 만제 ] 을 반환하는 경우
- a_stack[-1] 이 숫자를 반환하는 경우
1번의 경우엔, )을 pop 하여 a_stack에서 제거해 주었으며, a_stack.append(2)를 해주었다.
2번의 경우엔, ]을 pop 하여 a_stack에서 제거해 주었으며, a_stack.append(3)을 해주었다.
3번의 경우엔 ) 또는 ] 이 나올 때까지, pop을 하여, nums 리스트에 추가해 주었으며,
) 또는 ] 을 만나게 된다면 각각 2*sum(nums), 3*sum(nums) 를 a_stack 에 추가해 주었다.
또한, stack이 비어있는데, 참조하지 않도록 조심하였다.
3. 코드
def compute(b_stack):
a_stack = []
while b_stack:
popped = b_stack.pop()
if popped == ')' or popped == ']':
a_stack.append(popped)
else:
if popped == '[' and a_stack and a_stack[-1] == ']':
a_stack.pop()
a_stack.append(3)
elif popped == '(' and a_stack and a_stack[-1] == ')':
a_stack.pop()
a_stack.append(2)
elif a_stack and isinstance(a_stack[-1], int):
nums = [a_stack.pop()]
while a_stack and isinstance(a_stack[-1], int):
nums.append(a_stack.pop())
if a_stack and a_stack[-1] == ')' and popped == '(':
a_stack.pop()
a_stack.append(2*sum(nums))
elif a_stack and a_stack[-1] == ']' and popped == '[':
a_stack.pop()
a_stack.append(3*sum(nums))
else:
return 0
else:
return 0
for s in a_stack:
if not isinstance(s, int):
return 0
return sum(a_stack)
if __name__ == "__main__":
b_stack = list(input())
print(compute(b_stack))
728x90
'코딩 테스트 > 백준' 카테고리의 다른 글
[백준 2024/09/11] 1655번 가운데를 말해요 (0) | 2024.09.11 |
---|---|
[백준 2024/09/11] 3190번 뱀 (0) | 2024.09.11 |
[백준 2024/09/10] 2493번 탑 (0) | 2024.09.10 |
[백준 2024/09/10] 1629번 곱셈 (0) | 2024.09.10 |
[백준 2024/09/10] 2630번 색종이 만들기 (0) | 2024.09.10 |